2

这可能是一个简单的问题，但我需要以不同的方式来做。问题是我必须在序言中找到可能的飞行路线。我有这个知识库

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

我必须创建一个谓词 route(X,Y) 来检查我们是否可以从 X 到 Y。我所做的是：

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

但它不起作用，因为图形是循环的。我在互联网上搜索，每个人都说的唯一一件事就是使用列表并检查访问过的路径。但我不能使用列表！我必须在不使用列表的情况下创建谓词路由（X，Y），如果没有列表，我该如何完成呢？谢谢

4

4 回答 4

1

So you can't use lists (I wonder why) but can you use a counter variable? Try iteratively deepening search where you do depth-first search first in the depth of 1, then 2, and so on. That would prevent the infinite loops with cycles.

Remember to have an upper limit for search depth to avoid infinite looping in case where there is no connection.

于 2014-11-27T06:45:59.870 回答
1 
route(X0,X) :-
   from_to(X0,X1),
   closure0(from_to,X1,X).

See this question for a definition of closure0/3.

于 2014-11-26T22:49:46.250 回答
1

如果您没有严格要求使用 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-27T04:45:42.007 回答
0

我会尝试

:- 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-26T23:50:53.347 回答