1

我有一个任务要写，一组序言谓词确定任何两个二叉树是否彼此同构。谓词还必须能够为任何给定的二叉树提供所有同构图。

到目前为止，这是我所拥有的，除了返回重复项外，它都有效。

% 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)).

显然这些都是重复的，我似乎找不到合适的位置来放置剪切，因此谓词不会返回重复项。我还尝试为只有一个叶子的节点和另一个节点编写另外两个谓词，但它们似乎没有帮助。

关于如何停止重复的任何建议？

4

1 回答 1

1

想想当 BT = node(leaf, X, Leaf) 时会发生什么。对于这种情况，您的解决方案会产生两个相同的解决方案。一个叶子交换的地方，一个不交换叶子的地方。

您需要明确处理这种情况，只返回一个解决方案。由于这种情况可能看起来像其他条款，您还需要确保这种情况不能由多个条款满足。

于 2009-10-12T04:53:12.420 回答