Prolog无限循环（循环图）

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

请参见this question以获取closure0/3的定义。

Answer 2

如果不严格要求您使用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 3

所以您不能使用列表（我想知道为什么），但是可以使用计数器变量吗？尝试iteratively deepening search，首先在深度1中进行深度优先搜索，然后在深度2中进行搜索，依此类推。这样可以防止带有循环的无限循环。

请记住对搜索深度有上限，以避免在没有连接的情况下无限循环。

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

但是在第一次调用后，需要重新加载KB。