問題中的遞歸決策樹

Question

所以我試圖畫出2個Prolog問題樹的決定，一個使用累加器，另一個不使用累加器。這裏是我的問題和解決辦法我沒分別，：

length([H|T],N) :- length(T,N1), N is N1+1. 
length([ ],0). 
Goal: ?: length([1,2,3],N) 

第二個累加器：

length_acc(L,N) :- len_acc(L,0,N). 
len_acc([H|T], A, N) :- A1 is A+1, len_acc(T, A1, N). 
len_acc([], A, A). 
Goal: ?-length_acc([1,2], N). 

是決策樹正確繪製？還是我犯了一個錯誤？什麼是繪製這種遞歸決策樹的正確方法？

感謝。

Answer 1

您所指的樹通常稱爲搜索樹又名SLD樹，不要與證明樹混淆。

兩個你所概述的問題是搜索樹的最簡單的例子：

• 只有一個解決方案
• 查詢不會失敗
• 在搜索的每一步只能匹配單個子句（空列表與非空列表）

這三個特徵意味着SLD樹中只有一個分支。

你會得到下面的搜索樹：

注意，它是一個正確的搜索樹，最多一個目標是在每個解決這使得搜索樹非常大......因此人們常常會在每一步中解決多個目標的簡化樹，這可能不是真正的搜索樹，而是以更簡潔的方式說明了搜索。

樹中的邊緣被替換標記，這些替換作爲統一算法的一部分應用於變量。

搜索樹與痕跡密切對應，您通常可以從程序的蹤跡到搜索樹進行直接翻譯。

我建議你研究具有多個答案和可能失敗的分支的查詢的搜索樹，這會給出更多有趣的樹與多個分支。從序言中的技術人員通過英鎊，夏皮羅一個例子：

計劃：

father(abraham, isaac).  male(isaac) 
father(haran, lot).   male(lot). 
father(haran, milcah).   female(milcah). 
father(haran, yiscah).   female(yiscah). 

son(X,Y):- father(Y,X), male(X). 
daughter(X,Y):- father(Y,X), female(X). 

查詢：

?: son(S, haran) 

搜索樹：