問題の再帰的決定木

Question

私は2つのPrologの問題の木の決定を描こうとしています、1つはアキュムレータを使用し、もう1つはそうではありません。ここでは、それぞれ、自分の問題と私がしたソリューションです：

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

アキュムレータと第二1：

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ツリーと呼ばれます。あなたが概説されている

問題の両方が検索ツリーの最も簡単な例です：

• クエリは、検索の各ステップだけ一致させることができます
• を失敗しない唯一の解決策
• があります

これらの3つの特性は、SLDツリーに1つのブランチしか存在しないことを意味します。

あなたが買ってあげる、次の検索-木：それは正しい検索ツリーをするためほとんどで、目標はそれぞれに解決されることを

注意これは検索木が非常に大きくなるため、人々が各ステップで複数の目標を解決できるような単純化されたツリーを作成するのはよくあることですが、これはおそらく真の検索ツリーではありませんが、

ツリー内のエッジは、統一アルゴリズムの一部として変数に適用される置換でラベル付けされています。

検索ツリーはトレースと密接に対応しており、通常はプログラムのトレースから検索ツリーに直接変換できます。

複数の回答と失敗する可能性のある分岐の検索ツリーを調べることをお勧めします。複数の分岐を持つより興味深いツリーが表示されます。スターリング、シャピロによってプロローグのアートから例：

プログラム：

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) 

検索ツリー：