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

Question

Вот код

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. 

Answer 1

Одно предостережение мой ответ - я делаю несколько предположений о ваших переменных. Я предполагаю, что 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. 

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

Сообщите мне, если это поможет.

Answer 2

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

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

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

?- route(roc, syr, [], Routing, Duration).