Рекурсия Prolog делает бесконечный цикл

Вот код

flight(roc,syr,25).
flight(roc,jfk,55).
flight(jfk,bos,65).
flight(bos,syr,40). 
flight(jfk,syr,50). 
flight(bos,roc,50).

layover(roc,25). 
layover(jfk,55).
layover(syr,30).  
layover(bos,40).

route(X,Y,R,D) :-
   flight(X,Y,L),
   D is L,
   R = [X,Y].
route(X,Y,R,D) :-
   flight(X,Z,L),
   route(Z,Y,P,M), 
   R = [X|P],
   layover(Z,T),
   D is M+L+T,
   \+ member(X,P).

Вот что происходит. Второй пункт

route(X,Y,R,D) :-
   flight(X,Z,L),
   route(Z,Y,P,M), 
   R = [X|P], 
   layover(Z,T),
   D is M+L+T,
   \+ member(X,P).

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

Вот одно решение

?- route(roc, syr, Routing, Duration).
Routing = [roc, syr],
Duration = 25 ;
Routing = [roc, jfk, syr],
Duration = 160 ;
Routing = [roc, jfk, bos, syr],
Duration = 255 ;
false.

recursion infinite prolog
person Khalil Norman    schedule 29.04.2013    source источник

Ответы (2)


arrow_upward
0
arrow_downward

Одно предостережение к моему ответу: я делаю несколько предположений о ваших переменных. Я предполагаю, что X — начальная точка, Y — пункт назначения, R — список мест на пути от X до Y (включительно), а D — пройденное расстояние? Или, возможно, время ожидания. Не должно иметь значения.

Это похоже на проблему с вашим базовым случаем. Ваш базовый случай проверяет наличие flight(X,Y,L), удовлетворяющего маршруту. Что вам нужно проверить, так это то, что список местоположений от X до Y (R, если я не ошибаюсь) уже охватывает от X до Y. То есть, если последний элемент списка R = Y и первый элемент R = X, то все готово.

Последняя функция, которую вы могли бы использовать, была бы:

last([X],X).
last([H|T],R):- last(T,R).

Тогда у вас может быть базовый случай:

route(X,Y,R,D):- last(R,L), L == Y, [H|T] = R, H == X.

Или что-то в этом роде. Прошло некоторое время с тех пор, как я использовал prolog...

Дайте мне знать, если это поможет.

person jwest    schedule 29.04.2013
comment
Думаю, я не объяснил все переменные. R - маршрут, D - расстояние (нужно считать при остановке). R и D — это ответы, поэтому я не вставляю их, когда вызываю правило. Не уверен, что то, что вы предложили, правильно. В случае маршрута, который вы указали, откуда берутся H и T, а D никогда не определяется. - person Khalil Norman; 30.04.2013
comment
?- route(roc, syr, Routing, Duration). Routing = [roc, syr], Duration = 25 ; Routing = [roc, jfk, syr], Duration = 160 ; Routing = [roc, jfk, bos, syr], Duration = 255 ; ложный. - person Khalil Norman; 30.04.2013

arrow_upward
0
arrow_downward

Я думаю, что ваша проблема должна быть решена перемещением \+member(X,P) перед рекурсивным вызовом. Это связано с тем, что Пролог реализует логику с помощью поиска в глубину предложений, т. е. выбора и сопоставления сверху вниз и слева направо.

Конечно, перенос теста требует изменения P вычислений. Сейчас строится после визита. Простой способ сделать это — использовать аккумулятор, инициализированный [] при первом вызове и унифицированный до полного пути в месте назначения. т.е.

route(X,Y,Acc, [X,Y|Acc], D) :- flight(X,Y,L), D is L.
...

?- route(roc, syr, [], Routing, Duration).
person CapelliC    schedule 30.04.2013