Prolog Pathfinding с приоритетом

Question

У меня есть задание написать программу Prolog, в которой перечислены пути между двумя подземными станциями (метро), но она должна благоприятствовать путям с меньшими изменениями строки (она должна оставаться как можно дольше в той же строке до коммутационные линии).

Я придумал макет сценария и этот код, в то время как он правильно перечисляет некоторые пути (я знаю, что мне все еще нужно закодировать обнаружение цикла), не расставляет приоритеты в сегментах с одинаковой линией, как следовало бы.

Мой маршрутизатор:

route(X,Y,[drive(X,Y,L)],_) :- road(X,Y,L). 

%route(From, To, Directions, Lines_Visited). 
route(X,Y,[drive(X,Z,L)|R],Ls) :- 
    take(Ls,L,_),  %prioritise same-line paths 
    road(X,Z,L), 
    route(Z,Y,R,Ls), !. 

route(X,Y,[drive(X,Z,L)|R],Ls) :- 
    road(X,Z,L),  %if no same-line pathes exist, try different line 
    route(Z,Y,R,[Ls|L]). 

Где взять/3 является

take([H|T], H, T). 

Один тестовый сценарий будет:

road(a,b,x). 
road(b,c,x). 
road(c,d,x). 
road(d,e,x). 
road(e,f,x). 
road(b,f,y). 
road(f,g,x). 

%a - b - c - d - e - f - g 
% |_______________| 

Если я пытаюсь маршрут (а, е, X). Я бы получил путь a -> b -> f, который меняет строки один раз, а THEN - однострочный путь a-> b-> c-> d-> e-> f.

По-видимому, моя приоритизация не работает, и я не могу придумать другой способ сделать это. Может кто-то пролить некоторый свет и указать мне на направление, чтобы решить эту проблему более эффективно?

Answer 1

Ваш код нуждается в значительной реструктуризации. В принципе, вы вообще не используете информацию о том, какая строка используется в текущем пути (take/3 бесполезно, поскольку она не связывает третий аргумент). Вот мой пример. Добавьте обнаружение петли, теперь, когда у вас есть 'видели до сих пор' узлы ...

%route(From, To, Directions, Lines_Visited). 
route(X,X,RPath,Path) :- reverse(RPath,Path). 
route(X,Y,[Last|R],Ls) :- 
    Last = [drive(X,Z,L)|_], %prioritise same-line paths 
    road(X,Z,L), 
    route(Z,Y,R,Ls). 
route(X,Y,PathSoFar,Ls) :- 
    road(X,Z,L),  %if no same-line pathes exist, try different line 
    route(Z,Y,[road(X,Z,L)|PathSoFar],Ls). 

тест:

?- route(a,f,[],X). 
X = [road(a, b, x), road(b, c, x), road(c, d, x), road(d, e, x), road(e, f, x)] ; 
X = [road(a, b, x), road(b, f, y)] ; 
false.