在Prolog路由規劃器中出現本地堆棧錯誤

Question

我正在嘗試在城鎮之間編寫Prolog路由規劃器。這裏是我的代碼：

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之間的城鎮列表，找到兩個城鎮之間的總體距離。

當我運行route時，它有時有效，其他時間我得到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之間的路由不存在。有誰知道我爲什麼會遇到錯誤？

Answer 1

序言中的規則是左繼續。 在你你做了最後一條規則：

routen(X,Y,N) :- routen(X,Z,N1),routen(Z,Y,N2),N is N1+N2,!. 

至極它使你的程序嘗試對規則routen（X，Z，N1）無限次。這意味着在某一時刻，堆疊將會滿了。

這裏發生了什麼：

1. 找到米斯克裏的路線。

2. 它不存在城市之間的直接道路：試圖找到另一箇中間城市。它找到了meath-dublin。

3. 然後它嘗試都柏林克裏。但是，它並不是在城市之間建立直接的道路：試圖找到另一箇中間城市。它找到了都柏林基爾代爾。等等。

4. 最後它找到了micklow-wexford。所以到目前爲止發現的路線是：meath-dublin-kildare-wicklow-wexford。

5. 現在嘗試韋克斯福德-凱瑞與第一

   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它試圖與所述第一規則

   routen(wexford,kerry,N) :- road(wexford,kerry,N). 
   

   失敗，導致它們之間不存在直接的通路。因此，它呼籲：

   routen(wexford,kerry,N) :- road(wexford,Z,N1),road(Z,kerry,N2),N is N1+N2. 
   

   其失敗原因不能satify

   road(wexford,Z,N1). 
   

   最後，它會嘗試與最後一條規則

   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,!. 
   

6. 它試圖滿足第一個一個

   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

正如你所看到的，它永遠不會發現城市「克里「，它陷入無限循環。

這裏的新代碼：

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. 

注意，在最後一個規則，我把

road(X,Z,N1) 

routen(Z,Y,N2) 

之前那麼，如果該機構的第一句話失敗，你永遠不會陷入與第二個循環。