Проблема с получением списка путей поездки в Прологе

У меня возникли проблемы со следующей проблемой в Prolog, например, у меня есть несколько фактов в базе знаний:

flight(rome,london,ba,1500,150,400).
flight(london,newyork,airfrance,600,60,200).
flight(rome,paris,airfrance,1200,120,500).  
flight(paris,newyork,airfrance,600,60,200).
flight(newyork,london,ba,1500,240,300).

Меня интересует только получение списка всех возможных маршрутов из X в Y. Я понимаю, что должен использовать рекурсивное правило и что я должен добавить посещенные места в список, чтобы остановить цикл, повторяющийся снова и снова, поскольку пути полета в базе знаний есть несколько циклов.

что у меня есть до сих пор:

flight_route(X,Y):-
   flight(X,Y,A,B,C,D).

trip(X,X,[]).
trip(X,Z,T) :-
   flight_route(Y,Z),
   not(member(Y,T)),
   trip(X,Y,[Y|T]).

по какой-то причине, когда я смотрю на трассировку, правило не работает, когда оно пытается проверить, что не (член (Y, T)) но я не могу понять, почему это так.


list recursion prolog transitive-closure
person user2928132    schedule 02.11.2014    source источник

Ответы (2)


arrow_upward
1
arrow_downward

В более общем смысле,

trip(X,Y) :-
   closure0(flight_route,X,Y).

См. определение closure0/3.

person false    schedule 21.11.2014

arrow_upward
0
arrow_downward

Проблема в вашем определении предиката trip/3. Пытаться:

trip(X, X, _).
trip(X, Z, T) :-
   flight_route(X, Y),
   \+ member(Y, T),
   trip(Y, Z, [Y| T]).

В первом предложении, когда вы находитесь в пункте назначения, не имеет значения, как вы туда попали. Отсюда и (анонимная) переменная в третьем аргументе. Кроме того, вероятно, эффективнее найти путь, начинающийся из исходной точки, а не из точки назначения. Возможная проблема также может заключаться в том, как вы вызываете предикат trip/3. Обязательно вызовите его с пустым списком, переданным третьим аргументом (если вы не заземлите T, вызов \+ member(Y, T) всегда будет завершаться ошибкой). Или определите аргумент trip/2, чтобы абстрагироваться от этой детали реализации:

trip(X, Y) :-
    trip(X, Y, []).
person Paulo Moura    schedule 02.11.2014
comment
Спасибо за ваш ответ, я вижу, как ваше предложение имеет смысл, но одна вещь, в которой я не уверен, это как написать список T. После внесения предложенных вами изменений я могу запросить, например, (rome, newyork). который возвращает Истина. Однако я не уверен, как вернуться и записать в консоль все возможности списка T. Когда я запрашиваю (rome, newyork, T). Я получаю ложный результат. Еще раз спасибо за ваш совет. - person user2928132; 02.11.2014
comment
Подсказка: вы можете использовать дополнительный аргумент, чтобы вернуть путь между двумя соединенными аэропортами. Аргумент (текущий) списка предназначен только для того, чтобы избежать циклов. - person Paulo Moura; 02.11.2014
comment
Спасибо за ответ, Пауло. Думаю, теперь я понял. - person user2928132; 12.11.2014