Пролог: обработка циклов при обходе графа

road(london, paris, 135).
road(paris, london, 135).
road(paris, madrid, 250).
road(madrid, paris, 250).
road(madrid, barcelona, 70).
road(barcelona, madrid, 70).

route(X, Y, [X|Y], N) :-
   road(X, Y, N).
route(X, Y, [X|T], N) :- 
   road(X, Z, A),
   route(Z, Y, [_|T], B),
   N is A + B.

Это пример кода проблемы, с которой я столкнулся. Мой тестовый ввод

?- route(london, barcelona, R, 455).

Этот вход будет повторяться через лондон-париж и париж-лондон, однако я заметил, что он найдет маршрут из лондон-барселона, если я удалю цикл париж-лондон.

Мой вопрос в том, могу ли я каким-либо образом реализовать предикат, который позволит мне игнорировать цикл.


graph-traversal graph-theory cycle prolog
person padraic    schedule 14.12.2015    source источник
comment
Используйте memberchk/2 и другой аргумент, чтобы убедиться, что вы не рассматриваете место, которое уже использовали.   -  person Daniel Lyons    schedule 14.12.2015
comment
это route(X, Y, [X|Y], N) :- road(X, Y, N). определенно неверно: Y — это атом, а не список   -  person CapelliC    schedule 14.12.2015

Ответы (2)


arrow_upward
2
arrow_downward

Вы можете сделать эти модификации:

road(london, paris, 135).
road(paris, madrid, 250).
road(madrid, paris, 250). 
road(madrid, barcelona, 70).
road(barcelona, madrid, 70).

path(From, To, List, N) :-
   route(From, To, [From], N).

route(X, Y, Passed_city, N) :-
   road(X, Y, N).
route(X, Y, Passed_city, N) :- 
   road(X, Z, A),
   \+ member(Z, Passed_city),
   route(Z, Y, [Z|Passed_city], B),
   N is A + B.

и вызовите запрос

?- path(london, barcelona, R, 455).

Что я сделал, так это создал новое правило для path/4, чтобы вставить первый город Откуда в список, содержащий все города, которые вы проехали, например: route(From, To, [From], N).

Затем я вставил цель \+ member(Z, Passed_city) в тело второго правила.

\+ означает «недоказуемый», поэтому \+ member(Z, Passed_city) истинно, если member(Z, Passed_city) терпит неудачу, то есть, если Z не находится в Passed_city.

person s.dallapalma    schedule 14.12.2015
comment
s(X), но как насчет третьего аргумента path/4, List? Эта переменная несколько отключена... преднамеренно? - person repeat; 14.12.2015
comment
Да, это список, который содержит все города пути. Итак, в london-barcelona он содержит [barcelona, ​​madrid, paris, london] - person s.dallapalma; 14.12.2015

arrow_upward

arrow_downward

person    schedule
comment
Добро пожаловать в Stackoverflow. Пожалуйста, опубликуйте объяснение или описание вашего кода. Предполагается, что ответ должен содержать больше, чем просто код в stackoverflow, иначе он будет закрыт. - person Akshay Hazari; 21.01.2016