1

我正在使用 SWI Prolog 研究 Prolog，我发现这个代码片段有很多困难，如果 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.

我认为如果第一棵树与第二棵树有 N 个公共子树，那么delta/3谓词是正确的

他以这种方式说唱这棵树：

tree(F, LIST_OF_SUBTREES).

例如，这是一棵由根 X 和两片叶子 u 和 v 组成的树：

tree(x, [tree(u,[]), tree(v,[])])

我认为delta/3谓词被拒绝为 3 种可能的情况：

1) T1 和 T2 是仅由根 X 组成的两棵树，因此它们只有一个公共子树是正确的

**2) T1 和 T2 是不同的，并且是具有更多级别的结构化树，因此如果 T1 和 T2 具有 N 个子树，则为 TRUE：？！？！

3) 否则，如果前面的 delta\2 谓词都失败了，那么无论 T1 和 T2 是否它们有 0 个公共树都是真的

我认为这种解释是正确的（我希望如此......）但我在理解第二条规则时遇到了一些困难：什么可能是sons/2谓词（在我看来，这是注意内置谓词的 SWI Prolog 和我在我正在学习的幻灯片上没有它的实现）

什么是给你的？它的逻辑是什么？

肿瘤坏死因子

安德烈亚

4

1 回答 1

1

你对这三个规则的解释在我看来是合理的。为了比较，我将它们改写为：

  1. delta(T1, T2, 1)如果 T1 和 T2 具有相同的值并且为空（叶节点），则成立。
  2. delta(T1, T2, N)如果 T1 和 T2 有 N 个公共子树，则成立。
  3. delta(T1, T2, 0)如果 T1 和 T2 有 0 个公共子树，则成立。

我不清楚为什么这些削减是必要的。我想它们是绿色切割，因为一对树不能同时有 1、N 和 0 个公共子树。

sons/2很有趣。我可以想象它以几种不同的方式工作。我们确定的一件事是，如果两棵树有共同的子树，sons/2则应该生成相同的值；它必须以这种方式工作，否则sons(RX, SX), sons(RX1, SX)将永远无法工作。（请注意，该行缺少逗号）。

剩下的一个问题是，是否sons/2通过生成所有子树或仅生成最近的一对来工作？在我看来，它可能只生成最近的对，因为subdelta/3调用delta/3会导致间接递归。如果sons/2生成所有子树，这将导致无限递归或至少大量不必要的工作。所以我敢打赌，sons/2看起来像这样：

sons(tree(_,Children), X) :- member(X, Children).

这表明至少有一种情况delta/3会比人们乍一看更智能：T1 和 T2 是彼此的反射。sons/2T1 和 T2 将左与右统一，然后将右与左统一，因此您将从共享子树中获得最大相似性，但不是精确结构。

最令我惊讶的是，这delta/3似乎没有计算差异，它似乎计算了相似之处。这不是人们对名称所期望的，但它是从实现中得出的。很难想象如何直接计算差异——上限是多少？例如，对于文件，您可以通过说每行可能相同 (0) 或不同 (1) 来计算差异，然后将差异相加。

希望这是在正确的轨道上并有所帮助！

于 2013-05-06T15:52:22.490 回答