Пролог не находит решения

Question

Моделирование остановок подземного трубопровода примерно так:

stop(line1, 1, station1).
stop(line1, 2, station2).
stop(line1, 3, station3).
stop(line1, 4, station4).
stop(line1, 5, station5).
stop(line2, 1, station2).
stop(line2, 2, station4).

где stop(L, N, S) означает S это N -ая остановка на линии L, я пытаюсь определить path(S1, S2, P), который вычисляет возможные пути между S1 и S2.

Здесь путь - это список «сегментов», сегмент - это путешествие по одной и той же линии, т. Е. segment(L,S1,S2) представляет непрерывное путешествие от S1 до S2 по линии L. Таким образом, возможное решение для path(a,d,P) - это P=[segment(line1, a, b), segment(line2, b, d)], то есть перейти от a до b на line1, затем перейти от b до d на line2.

Дополнительным ограничением является то, что путь не должен содержать одну и ту же строку более одного раза.

У меня есть следующее:

segment(L, S1, S2) :- stop(L, N1, S1), stop(L, N2, S2), N2>N1.
line_present_in_path(_, []) :- false.
line_present_in_path(L, [H|_]) :- segment(L, _, _) = H.
line_present_in_path(L, [_|T]) :- line_present_in_path(L, T).
path(S1, S2, [H]) :- segment(_, S1, S2) = H, H.
path(S1, S2, [H|T]) :- segment(L, S1, X) = H, H, \+line_present_in_path(L, T), path(X, S2, T).

но происходит нечто странное. Если я сам явно укажу все параметры, он распознает его как правильный путь:

?- path(station1, station4, [segment(line1, station1, station2),segment(line2, station2, station4)]).
true ;
false.

Однако, если я попрошу его рассчитать все пути, он найдет только один путь, отличный от пути, который он только что проверил как правильный:

?- path(station1, station4, P).
P = [segment(line1, station1, station4)] ;
false.

Я должен признать, что я новичок в Прологе, поэтому я мог упустить что-то простое. Но я действительно не могу понять, почему он может проверить заданный путь как правильный, но он не находит этот путь при попытке найти все пути.

Answer 1

Ошибка во втором предложении для предиката path/3. Переписав это для ясности:

path(S1, S2, [segment(L, S1, X)|T]) :-
    \+ line_present_in_path(L, T),
    path(X, S2, T).

С такой целью, как path(station1, station4, P), вы вызываете предикат line_present_in_path/2 с переменной во втором аргументе. Этот призыв всегда успешен, и поэтому его отрицание всегда терпит неудачу. В общем, вы должны быть осторожны с использованием \+/1 только с достаточно аргументированным аргументом.

Подсказка: чтобы устранить ошибку, используйте дополнительный аргумент к предикату пути для хранения найденных станций. Э.Г.

path(S1, S2, Path) :-
    path(S1, S2, Path, []).

path(S1, S2, Path, Visited) :-
    ...

Вы можете использовать де-факто стандартный предикат member/2, чтобы проверить, находится ли станция уже на пути, и в противном случае добавить ее в список посещенных. Поиск пути является распространенным вопросом, и вы найдете несколько связанных ответов здесь в StackOverflow. Но попробуйте сначала решить это самостоятельно.