Prolog路由计划器中的本地堆栈错误 [英] Out of local stack error in Prolog route planner
问题描述
我正在尝试编写城镇之间的Prolog路线规划器.这是我的代码:
I am trying to write Prolog route planner between towns. Here's my code:
road(meath,dublin,5).
road(dublin,kildare,9).
road(kildare,wicklow,7).
road(wicklow,wexford,10).
/*Rules:*/
route(X,Y,[H|_ ],N) :-
road(H,Y,_),
routen(X,Y,N1),
N is N1.
route(X,Y,[H|T],N) :-
road(X,H,_ ),
routen(X,Y,N1),
N is N1,
route(H,Y,T,_),
!.
route(X,Y,[],N) :-
road(X,Y,N1),
N is N1.
routen(X,Y,N) :-
road(X,Y,N).
routen(X,Y,N) :-
road(X,Z,N1),
road(Z,Y,N2),
N is N1+N2.
routen(X,Y,N) :-
routen(X,Z,N1),
routen(Z,Y,N2),
N is N1+N2,
!.
谓词road具有两个城镇以及它们之间的距离.规则route查找X和Y之间的城镇列表，而routen查找两个城镇之间的总距离.
The predicate road has the two towns and the distance between them. The rule route finds the list of towns between X and Y and routen finds the overall distance between two towns.
当我运行route时，它有时可以工作，而有时我会得到ERROR: Out of local stack.
When I run route, it sometimes works and other times I get a ERROR: Out of local stack.
示例:
?- route(meath,wexford,[dublin,kildare,wicklow],31).
true.
?- route(meath,wexford,[dublin,kildare,wicklow],30).
false.
?- route(meath,kerry,[dublin,kildare,wicklow],31).
ERROR: Out of local stack
最后一个应该返回false，因为meath和kerry之间的路由不存在.有人知道我为什么会出错吗?
The last one should return false, as a route between meath and kerry doesn't exist. Does anyone know why I am getting an error?
推荐答案
Prolog中的规则为左手删除. 在您的上一条规则中，您做到了:
Rules in Prolog are LEFT RECURSIVE. In you last rule you did:
routen(X,Y,N) :- routen(X,Z,N1),routen(Z,Y,N2),N is N1+N2,!.
它可以使您的程序无限次尝试规则 routen(X，Z，N1).这意味着在某一时刻堆栈将已满.
wich it makes your program try the rule routen(X,Z,N1) infinite times. This means that at one point the stack will be full.
这是怎么回事:
-
找到了一条从米斯到凯里的路线.
find a route from meath to kerry.
在城市之间不存在直接道路:尝试寻找另一个中间城市.它找到了都士都柏林.
It doens't exist a direct road between the cities: try to find another intermediate city. It find meath-dublin.
然后尝试使用都柏林凯利(dublin-kerry).但是，同样，它在城市之间不存在直接的道路:尝试寻找另一个中间城市.它找到都柏林基尔代尔.等等.
Then it try dublin-kerry. But, again, it doens't exist a direct road between the cities: try to find another intermediate city. It find dublin-kildare. And so on.
最后它到了，找到了米克洛-韦克斯福德.因此，到目前为止找到的路线是:Meath-dublin-kildare-wicklow-wexford.
Finally it arrives to find micklow-wexford. So The route found so far is: meath-dublin-kildare-wicklow-wexford.
现在，使用第一个
route(X,Y,[H|_ ],N) :- road(H,Y,_),routen(X,Y,N1), N is N1.
它满足第一个
road(H,Y,_)
然后减少
routen(X,Y,N1), N is N1.
5.1尝试第一个规则
5.1 It tries with the first rule
routen(wexford,kerry,N) :- road(wexford,kerry,N).
失败的
，因为它们之间不存在直接的道路.因此它称为:
that fails, cause doesn't exist a direct road between them. So it call:
routen(wexford,kerry,N) :- road(wexford,Z,N1),road(Z,kerry,N2),N is N1+N2.
由于无法满足而失败
road(wexford,Z,N1).
最后，它尝试使用最后一条规则
At the end, it tries with the last rule
routen(wexford,kerry,N) :- routen(wexford,Z,N1),routen(Z,kerry,N2),N is N1+N2,!.
因此减少了
routen(wexford,Z,N1),routen(Z,kerry,N2),N is N1+N2,!.
它试图满足第一个
It tries to satisfy the first one
routen(wexford,Z,N1).
使用
routen(X,Y,N) :- road(X,Y,N).
routen(X,Y,N) :- road(X,Z,N1),road(Z,Y,N2),N is N1+N2.
routen(X,Y,N) :- routen(X,Z,N1),routen(Z,Y,N2),N is N1+N2,!.
分别与
X=wexford
Z=DG51_ % or something like that. That is, an not instantiated variable
并重复步骤5.1
如您所见，它永远找不到克里"城市，并且陷入无限循环.
As you can see, it will never find the city "kerry" and it fall in an infinite loop.
这里是新代码:
road(meath,dublin,5).
road(dublin,kildare,9).
road(kildare,wicklow,7).
road(wicklow,wexford,10).
/*Rules:*/
route(X,Y,[H|_ ],N) :- routen(X,Y,N),!.
%route(X,Y,[H|T],N) :- road(X,H,_ ),routen(X,Y,N1), N is N1, route(H,Y,T,_).
route(X,Y,[],N) :- road(X,Y,N1), N is N1.
routen(X,Y,N) :- road(X,Y,N).
%routen(X,Y,N) :- road(X,Z,N1),road(Z,Y,N2),N is N1+N2.
routen(X,Y,N) :- road(X,Z,N1),routen(Z,Y,N2),N is N1+N2.
请注意，我的最后一条规则是
Notice that at the last rule I put
road(X,Z,N1)
之前
routen(Z,Y,N2)
因此，如果该正文的第一个子句失败，您将永远不会陷入与第二个子句的循环中.
So, if the first clause of that body fails, you'll never fall in a loop with the second one.
这篇关于Prolog路由计划器中的本地堆栈错误的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
