Пролог - Предикат для обнаружения подключенных узлов в ориентированном графике

Question

Я смотрел на этот вопрос, в котором мы делаем предикат в Прологе, который находит путь между двумя узлами («станциями метро») в ориентированном графе.Исходный код, предложенный ниже:

path(Start, Dest, [[Start,Dest]]) :- connected(Start, Dest).
path(Start, Dest, [[Start, Waypoint]|Path]) :- dif(Dest, Waypoint), 
    connected(Start, Waypoint), path(Waypoint, Dest, Path).

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

alldifferent(_,[]).
alldifferent(X,[L|Ls]) :- dif(X,L), alldifferent(X,Ls).

pathaux(Start, Dest, [Start,Dest],Q) :- connected(Start, Dest), alldifferent(Start,Q).
pathaux(Start, Dest, [Start, Waypoint|Path],Q) :- dif(Dest, Waypoint),
    connected(Start, Waypoint), 
    pathaux(Waypoint, Dest, Path, [Start|Q]), alldifferent(Start,Q).

path(X,Y,Z) :- pathaux(X,Y,Z,[]).

Однако, когда я добавляю правило, которое создает цикл

connected(ataba,naguib).
connected(naguib,sadat).
connected(sadat,opera).
connected(opera,dokki).
connected(opera,ataba). //Note this one

Я получаю бесконечную рекурсию!Как так?и как можно это исправить?

Answer 1

как получилось?

Сначала рассмотрим причину не прекращения вашей исходной программы:

<s>path(Start, Dest, [[Start,Dest]]) :- <b>false</b>, connected(Start, Dest)</s>.
path(Start, Dest, [[Start, Waypoint]|Path]) :-
   dif(Dest, Waypoint), 
   connected(Start, Waypoint),
   path(Waypoint, Dest, Path), <b>false</b>.

Только этот фрагмент отвечает за прекращение,И если это не прекращается, то же самое происходит и с вашей исходной программой.

Теперь к вашей другой программе.Кстати, ваше определение alldifferent/2 обычно пишется как maplist(dif(X), Xs).

<s>pathaux(Start, Dest, [Start,Dest],Q) :- <b>false</b>, connected(Start, Dest), alldifferent(Start,Q)</s>.
pathaux(Start, Dest, [Start, Waypoint|Path],Q) :-
   dif(Dest, Waypoint),
   connected(Start, Waypoint), 
   pathaux(Waypoint, Dest, Path, [Start|Q]), <b>false</b>,
   <s>alldifferent(Start,Q)</s>.

path(X,Y,Z) :- pathaux(X,Y,Z,[]).

Вы заметили разницу?Список немного отличается, и есть вспомогательный аргумент, но внутри фрагмента, никто не использует этот аргумент.Так что примерно так же.Таким образом:

Это новое определение столь же плохо (или хуже), что и ваша оригинальная программа!

Самое общее решение - здесь .См. fault-slice , чтобы узнать больше об этой технике, чтобы локализовать фактическую причину отсутствия завершения.