試圖通過遞歸計算步驟？

Question

這是一個立方體，其邊緣是定向的;它只能從左到右，從上到下，從上到下。

edge(a,b). 
edge(a,c). 
edge(a,e). 
edge(b,d). 
edge(b,f). 
edge(c,d). 
edge(c,g). 
edge(d,h). 
edge(e,f). 
edge(e,g). 
edge(f,h). 
edge(g,h). 

通過下面的方法，我們可以檢查我們是否可以從A-H去做例如：cango（A，H）。

move(X,Y):- edge(X,Y). 
move(X,Y):- edge(X,Z), move(Z,Y). 

隨着move2，我試圖執行所需步驟的impalement計數。

move2(X,Y,N):- N is N+1, edge(X,Y). 
move2(X,Y,N):- N is N+1, edge(X,Z), move2(Z,Y,N). 

我將如何實現這一點？

Answer 1

move2(X,Y,1):- edge(X,Y), ! . 
move2(X,Y,NN):- edge(X,Z), move2(Z,Y,N), NN is N+1 . 

Answer 2

算術評估在Prolog中照常進行，但作業不能正常工作。然後，你需要引入一個新變量遞增值：

move2(X,Y,N,T):- T is N+1, edge(X,Y). 
move2(X,Y,N,T):- M is N+1, edge(X,Z), move2(Z,Y,M,T). 

，並在第一次調用初始化N到0。這些附加變量（在我們的情況下爲T）通常稱爲累加器。

Answer 3

(is)/2對實例的第二個參數非常敏感。這意味着你不能以完全相關的方式使用它。你可以問X is 1+1.，你甚至可以問2 is 1+1.，但你不能問：2 is X+1。

因此，當您使用謂詞(is)/2進行編程時，您必須想象謂詞將與哪些模式一起使用。這種考慮容易導致錯誤，尤其是如果你剛開始的話。但不要擔心，更精通的程序員仍然陷入這樣的問題。

在幾個Prolog系統中有一個乾淨的選擇：在SICStus，YAP，SWI中有一個library(clpfd)它允許你表達整數之間的關係。通常這個庫用於約束編程，但你也可以用它作爲整數的安全和乾淨的替換(is)/2。更重要的是，這個庫通常是非常有效的編譯，使得生成的代碼在速度上可以與(is)/2相媲美。

 
?- use_module(library(clpfd)). 
true. 

?- X #= 1+1. 
X = 2. 

?- 2 #= 1+1. 
true. 

?- 2 #= X+1. 
X = 1. 

所以現在回到你的程序，你可以簡單的寫：

 
move2(X,Y,1):- edge(X,Y). 
move2(X,Y,N0):- N0 #>= 1, N0 #= N1+1, edge(X,Z), move2(Z,Y,N1). 

要求你現在得到的所有距離。

但還有更給它...

爲了確保move2/3實際終止，嘗試：

 
?- move2(A, B, N), false. 
false. 

現在我們可以肯定的是move2/3永遠終止。總是？ 假設你已經添加了進一步的邊緣：

edge(f, f). 

現在上面的查詢循環。但是你仍然可以使用你的程序來獲得你的優勢！ 確定節點的數量：

 
?- setof(C,A^B^(edge(A,B),member(C,[A,B])),Cs), length(Cs, N). 
Cs = [a, b, c, d, e, f, g, h], 
N = 8. 

所以最長路徑將採取僅7步驟！

現在你可以再問查詢，但現在通過限制N的值小於或等於到7：

 
?- 7 #>= N, move2(A,B, N), false. 
false. 

通過這種附加的約束，你有再終止定義！沒有更多的循環。