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.
答
一个告诫我的答案 - 我想提出有关的变量几个假设。我假设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 ...
让我知道这是否有帮助。
答
我觉得你的问题应该是在之前用\+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).
猜猜我没有解释所有的变量。 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