Пролог Бесконечный цикл (циклический граф)

Question

Это может быть простой проблемой, но мне нужно сделать это по-другому. Проблема в том, что я должен найти в прологе возможные маршруты полетов. У меня есть эта база знаний

from_to(fresno,seattle).
from_to(fresno,albany).          
from_to(albany,dallas).     
from_to(fresno,boston). 
from_to(dallas,seattle).         
from_to(dallas,albany).
from_to(seattle,dallas).           
from_to(seattle,omaha).         
from_to(atlanta,albany).
from_to(atlanta,dallas).
from_to(atlanta,boston).
from_to(omaha,atlanta).         
from_to(omaha,albany).
from_to(albany,seattle).

И я должен сделать маршрут предиката (X,Y), который проверяет, можем ли мы перейти от X к Y. Я сделал следующее:

route(X,Y):-from_to(X,Y).
route(X,Y):-from_to(X,Z), route(Z,Y).

Но это не работает, потому что график циклический. Я искал в Интернете, и единственное, что все сказали, это использовать список и проверять посещенные пути. Но я не могу использовать списки! Я должен сделать маршрут предиката (X,Y) без использования списков, как я могу сделать это без списка? Спасибо

Answer 1

route(X0,X) :-
   from_to(X0,X1),
   closure0(from_to,X1,X).

Смотрите этот вопрос для определения closure0/3,

Answer 2

Таким образом, вы не можете использовать списки (интересно почему), но вы можете использовать переменную счетчика? Попробуйте итеративно углубить поиск, где вы выполняете поиск в глубину, сначала в глубину 1, затем 2 и так далее. Это предотвратит бесконечные циклы с циклами.

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

Answer 3

Если вам не требуется строго использовать SWI-Prolog, вы можете легко сделать это в системе Prolog с поддержкой табулирования. В B-Prolog я просто добавил :- table route/2. и теперь это работает:

?- route(fresno, omaha).
yes

?- route(fresno, fresno).
no

?- route(atlanta, atlanta).
yes

?- route(atlanta, X).
X = albany ?;
X = dallas ?;
X = boston ?;
X = seattle ?;
X = omaha ?;
X = atlanta
yes

Answer 4

Я бы попробовал

:- dynamic visited/1.

route(X,Y) :- retractall(visited(_)), route_(X,Y).
route_(X,Y) :- from_to(X,Y).
route_(X,Y) :- from_to(X,Z), \+ visited(Z), asserta(visited(Z)), route_(Z,Y).

тестовое задание:

1 ?- route(fresno, omaha).
true ;
false.

2 ?- route(fresno, omaha).
true ;
false.

3 ?- route(fresno, fresno).
false.

4 ?- route(atlanta, atlanta).
true ;
false.

Поскольку граф определен в исходном коде, альтернативой может быть:

:- dynamic from_to/2.

route(X,Y):-retract(from_to(X,Y)).
route(X,Y):-retract(from_to(X,Z)), route(Z,Y).

но после первого вызова требуется перезагрузка базы данных.