Prolog的递归做无限循环

下面的代码Prolog的递归做无限循环

flight(roc,syr,25). 
flight(roc,jfk,55). 
flight(jfk,bos,65). 
flight(bos,syr,40). 
flight(jfk,syr,50). 
flight(bos,roc,50). 

layover(roc,25). 
layover(jfk,55). 
layover(syr,30). 
layover(bos,40). 

route(X,Y,R,D) :- 
    flight(X,Y,L), 
    D is L, 
    R = [X,Y]. 
route(X,Y,R,D) :- 
    flight(X,Z,L), 
    route(Z,Y,P,M), 
    R = [X|P], 
    layover(Z,T), 
    D is M+L+T, 
    \+ member(X,P).

这里发生了什么。第二个子句

route(X,Y,R,D) :- 
    flight(X,Z,L), 
    route(Z,Y,P,M), 
    R = [X|P], 
    layover(Z,T), 
    D is M+L+T, 
    \+ member(X,P).

进入无限循环。它显示我想要的答案，然后继续找到更多的答案（因为你可以保持循环基本停下来），并进行无限循环，直到停止。该计划应该找到所有可能的飞行路线，而不是停在路边。我知道为什么发生这种情况，但不知道如何更改我的代码来修复它。请帮忙。

这里有一个解决方案

?- route(roc, syr, Routing, Duration). 
Routing = [roc, syr], 
Duration = 25 ; 
Routing = [roc, jfk, syr], 
Duration = 160 ; 
Routing = [roc, jfk, bos, syr], 
Duration = 255 ; 
false.

来源

2013-04-29 Khalil Norman

一个告诫我的答案 - 我想提出有关的变量几个假设。我假设X是起点，Y是目的地，R是从X到Y（包含）沿路径的位置列表，D是行进的距离？或者等待时间。应该不重要。

这看起来像是一个基本情况的问题。您的基本情况是检查是否存在符合路线的flight(X,Y,L)。你需要检查的是，从X到Y的位置列表（如果我没有弄错的话）已经从X覆盖到Y.也就是说，如果列表R的最后一个元素是Y，并且R的第一个元素= X，那么你就完成了。

你可以使用

最后一个功能是：

last([X],X). 
last([H|T],R):- last(T,R).

然后你就可以有一个基本情况：

route(X,Y,R,D):- last(R,L), L == Y, [H|T] = R, H == X.

或者类似的东西，反正。它已经有一段时间，因为我已经使用prolog ...

让我知道这是否有帮助。

来源

2013-04-29 23:11:17 jwest

猜猜我没有解释所有的变量。 R是路线，D是距离（必须在中途停留）。 R和D是答案，所以当我打电话给规则时我不会把它们放进去。不知道你的建议是否正确。在你给出的路线案例中，H和T从何而来，而D从未被定义过。 – 2013-04-30 00:19:37

？ - 路由（roc，syr，路由，持续时间）。 Routing = [roc，syr]， Duration = 25; Routing = [roc，jfk，syr]， Duration = 160; Routing = [roc，jfk，bos，syr]， Duration = 255; 错误。 – 2013-04-30 00:31:32

我觉得你的问题应该是在之前用\+member(X,P)来解决递归调用。这是因为Prolog通过深度优先执行逻辑搜索子句，即从上到下和从左到右选择和匹配。

当然，移动测试需要更改P的计算。现在是在访问后建成的。一个简单的方法是使用累加器，在第一次调用时初始化为[]，并统一到目标上的完整路径。即

route(X,Y,Acc, [X,Y|Acc], D) :- flight(X,Y,L), D is L. ... ?- route(roc, syr, [], Routing, Duration).

来源

2013-04-30 05:39:40 CapelliC

Prolog的递归做无限循环

回答

相关问题