私は SWI Prolog を使用して大学の試験のために Prolog を勉強していますが、述語を実装するこの例で教師が何をしているのかを理解するのにいくつかの問題があります (私には不完全に思えます)。
k(T1,T2,N)
T1 と T2 がツリーであり、それらがちょうど N 個のサブツリーを共有している場合(このサブツリーが T1 と T2 の両方に存在する場合、サブツリーは T1 と T2 の 2 つのツリー間で共通です) である場合、 TRUEです。
彼は別の述語T(t)を与えてくれました。ここで、t は特定のツリーであり、T(t) は t のすべてのサブツリーを与えてくれます (このことのグラフィカルな解釈を見たい場合は、このファイルのスライド 18 を参照してください: http ://www.informatica.uniroma2.it/upload/2012/LPDA/08_Lezione_ZNZ.pptx )
それで彼はこう言います：
k(T1,T2,N)
がTRUEの場合、TRUE は次の場合です。
実際には、T1 のサブツリー (T(T1) 述語から与えられる) と T2 のすべてのサブツリー (T(T2) から与えられる) の共通部分が真である場合、ツリー T1 と T2 が N 個の共通サブツリーを持つことは TRUE です。 predicate) はモジュール内で正確に N です (つまり、数値として)
では、続けてください。彼は次の方法でツリーを定義します。
tree(F, LIST_OF_SUBTREES).
ここで、R は現在のツリーのルートです
したがって、前のプロパティを使用して、ツリー T1 と T2 に N 個の共通サブツリーがある場合に TRUEになる述語k(T1,T2,N)を実装します。
この述語は、ツリー T1 および T2 のサブツリーの EXAUSTIVE SEARCHを使用する必要があります。
次に、 k/3述語を次のように実装します。
k(T1,T2,N) :- t(T1, ST1),
t(T2, ST2),
intersect(ST1,ST2,LST),
lenght(LST,N).
これは私にはかなり明確に思えます（間違っている場合は修正してください）：
- t(T1,ST1) T1 に含まれるすべてのサブツリーのリストを ST1 に入れる
- t(T2,ST2) T2 に含まれるすべてのサブツリーのリストを ST2 に入れる
- intersect(ST1,ST2,LST) ST1 と ST2 の共通サブツリーのリストを LST に入れます
- length(LST,N) ST1 と ST2 の共有サブツリーの長さを N に入れる
したがって、述語k(T1,T2,N)は、計算された N の値が与えられた N の値と一致する場合に真になります。
ここまでは、すべてが明確だと思います... しかし、ツリー T を取り、そのすべてのサブツリーのリストを STL に入れる **t(T,STL) 述語を彼がどのように実装するかを理解するのにいくつかの問題があります。
彼は私に次のコードを教えてくれました：
t(T,STL) :- bagof(ST, st(T,ST), STL).
st_r(tree(A,_), tree(A,[]).
st_r(tree(A,R), tree(A,R1) :- st_l(R,R1).
st_l([],[]).
st_l([X|R],[X1|R1]) :- st(X,X1),
st_l(R,R1).
st(T,T1) :- st_r(T,T1).
st(tree(A,R),T1) :- member(T,R),
st(T,T1).
述語について：
t(T,STL) :- bagof(ST, st(T,ST), STL).
STがサブツリーオブジェクトである述語に組み込まれたbagofを実行するだけで、目標st（T、ST）がSTLリスト（サブツリーのリスト）に入れられる場合、それを実行すると思います
しかし今、私はst/2述語 (私の目標) がどのように機能するかを理解していません!!! この述語と関連するst_l/2およびst_r/2述語の論理を説明してくれる人はいますか?
また、このプログラムのテストに使用できる 2 つのツリーを具体的に構築する方法についても疑問があります。テストに使用する 2 つの単純なツリーを教えていただけますか?
最後に、この例では、 intersect/3述語が欠落していると思います
TNX
アンドレア