1

とりわけ、2 つのバイナリ ツリーが互いに同型であるかどうかを判断する一連のプロローグ述語を作成する割り当てがあります。また、述語は、すべての同型グラフを任意のバイナリ ツリーに提供できなければなりません。

これが私がこれまでに持っているものです。重複を返すことを除いて機能します。

% Clause: btree_iso
%
% Specification:
% --------------
% Satisfied when the two binary-tree parameters are isomorphic. Two binary
% trees are isomorphic if one can be derived from the other by changing the
% order of the branches. Either of the parameters may be instantiated with a
% variable when btree_iso is used in a top-level goal.
%
% Description:
% ------------
% Base case for the binary tree iso morphism predicate.
% Both sides are leaves.
btree_iso( leaf, leaf ).

% Description:
% ------------
% TODO
btree_iso( node( BTL1, X, BTR1 ), node( BTL2, X, BTR2 ) ) :- btree_iso( BTL1, BTL2 ),
                                                             btree_iso( BTR1, BTR2 ).
% Description:
% ------------
% TODO
btree_iso( node( BTL1, X, BTR1 ), node( BTL2, X, BTR2 ) ) :- btree_iso( BTL1, BTR2 ),
                                                             btree_iso( BTR1, BTL2 ).

期待される出力: 

? - btree_iso(node(node(leaf,3,leaf),3,node(leaf,5,leaf)),BT).
BT = node(node(leaf, 3, leaf), 3, node(leaf, 5, leaf)) ;
BT = node(node(leaf, 5, leaf), 3, node(leaf, 3, leaf)).

私の出力

?- btree_iso(node(node(leaf,3,leaf),3,node(leaf,5,leaf)),BT).
BT = node(node(leaf, 3, leaf), 3, node(leaf, 5, leaf)) ;
BT = node(node(leaf, 3, leaf), 3, node(leaf, 5, leaf)) ;
BT = node(node(leaf, 3, leaf), 3, node(leaf, 5, leaf)) ;
BT = node(node(leaf, 3, leaf), 3, node(leaf, 5, leaf)) ;
BT = node(node(leaf, 5, leaf), 3, node(leaf, 3, leaf)) ;
BT = node(node(leaf, 5, leaf), 3, node(leaf, 3, leaf)) ;
BT = node(node(leaf, 5, leaf), 3, node(leaf, 3, leaf)) ;
BT = node(node(leaf, 5, leaf), 3, node(leaf, 3, leaf)).

明らかに、これらはすべて繰り返しです。カットを配置する適切な場所が見つからないように見えるため、述語は重複を返しません。また、リーフが 1 つしかないノードと、もう 1 つのノードに対して、他の 2 つの述語を書き込もうとしましたが、役に立たなかったようです。

重複を止める方法について何かアドバイスはありますか?

4

1 に答える 1

1

BT = ノード (リーフ、X、リーフ) の場合に何が起こるか考えてみてください。あなたのソリューションは、この場合に 2 つの同一のソリューションを生成します。葉が入れ替わっているところとそうでないところ。

このケースを明示的に処理して、1 つのソリューションのみを返す必要があります。このケースはおそらく他の句と同じように見えるため、このケースが複数の句で満たされないようにする必要もあります。

于 2009-10-12T04:53:12.420 に答える