Prolog路由计划器中的本地堆栈错误

Prolog路由计划器中的本地堆栈错误

本文介绍了Prolog路由计划器中的本地堆栈错误的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

限时删除!!

我正在尝试编写城镇之间的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查找XY之间的城镇列表,而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,因为meathkerry之间的路由不存在.有人知道我为什么会出错吗?

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.

这是怎么回事:

  1. 找到了一条从米斯到凯里的路线.

  1. 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路由计划器中的本地堆栈错误的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

    1403页,肝出来的..

  • 09-07 02:33