私は SWI Prolog を使用して Prolog を stufying しており、2 つのバイナリ ツリーに N 個の共通サブツリー (同じルートを持つ) がある場合に見つかったこのコード スニペットで多くの困難を見つけています。
/* BASE CASE: T1 and T2 are two tree composed of only the root X so it is
TRUE that they have exactly one common subtree
*/
delta(tree(X,[]),tree(X,[]),1):- !.
/* RULE: T1 and T2 are DIFFERENT and are structured tree.
It is TRUE that T1 and T2 have N subtrees if it is TRUE that:
*/
delta(tree(X,RX),tree(X,RX1),N):- sons(RX,SX),
sons(RX1,SX)
subdelta(RX,RX1,N),
!.
/* Else whatever T1 and T2 it is true that they have 0 common tree
(here we are in the case that the previous delta\2 predicate are
boot failed)
*/
delta(_,_,0):- !.
subdelta([],[],1).
subdelta([T1|R1],[T2|R2], N):-
delta(T1,T2,N1),
subdelta(R1,R2, NR),
N is (1 + N1)*NR.
最初のツリーが 2 番目のツリーと N 個の共通のサブツリーを持っている場合、 delta/3述語は true であると思います
彼はこの木を次のように表現します。
tree(F, LIST_OF_SUBTREES).
たとえば、これはルート X と 2 つのリーフ u と v で構成されるツリーです。
tree(x, [tree(u,[]), tree(v,[])])
delta/3の述語は、次の 3 つのケースに分類されると思います。
1) T1 と T2 はルート X のみで構成される 2 つのツリーであるため、それらが 1 つの共通サブツリーを持っていることは TRUE です。
**2) T1 と T2 は異なり、より多くのレベルを持つ構造化されたツリーであるため、T1 と T2 が N 個のサブツリーを持つことは TRUE です。
3) そうではなく、前の delta\2 述語の両方が失敗した場合、T1 と T2 が何であれ、それらの共通ツリーが 0 であることは true です。
この解釈は正しいと思います (そう願っています...) が、2 番目のルールを理解するのにいくつかの困難があります: sons/2述語とは何か (これは述語に組み込まれた SWI Prolog に注意してください。私が勉強しているスライドには実装されていません)
あなたにとって何ですか？そして、その論理は何ですか？
TNX
アンドレア