Prolog Infinite loop (циклический график)

Это может быть простая проблема, но мне нужно сделать это по-другому. Проблема в том, что я должен найти в прологе возможные маршруты полетов. У меня есть эта база знанийProlog Infinite loop (циклический график)

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) без использования списков, как я могу выполнить это без списка? Спасибо

источник

2014-11-26 SasukeItachi UchihaClan

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

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

источник

2014-11-26 22:49:46 false

спасибо за ваш ответ, но это все еще использует списки, я спрашиваю, возможно ли это без списков, это, безусловно, легкая проблема, потому что это первое упражнение, но я просто не могу этого сделать. –

@SasukeItachiUchihaClan: вы можете сделать это с помощью assert, но это очень склонно к ошибкам! – false

спасибо за информацию, упражнение действительно прост, но я не знаю, как это сделать, это действительно разочаровывает ... –

Я хотел бы попробовать

:- 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).

, но после первого звонка, требуется перезагрузка KB.

источник

2014-11-26 23:50:53 CapelliC

Не работает, если вы вызываете его более одного раза. – false

@false: вы не намерены разрабатывать? Кажется, на первый взгляд работает, и я попытался немного подтолкнуть к замене отсутствующей поддержки табуляции ... – CapelliC

'route (X, Y), route (Y, X)'. – false

Если вы не обязаны использовать 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

источник

2014-11-27 04:45:42

это так просто! Я вынужден к SWI, хотя, в любом случае спасибо –

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

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

источник

2014-11-27 06:45:59 drippingtap

ответ

Смежные вопросы