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的遞歸做無限循環

回答

相關問題