我们如何获得该值？

Question

你好 prolog 天才 :) 让我们考虑给定的数据库：

q3(t(V, nul, nul), 0).
q3(t(V, Q, nul), 1).
q3(t(V, nul, Q), 1).
q3(t(V, Q1, Q2), T) :- q3(Q1, T1), q3(Q2, T2), T is 1+T1+T2.

和以下查询

?- q3(t(4,
 t(2,
 nul,
t(3, t(1,nul,nul), t(9,nul,nul))),
 t(7, t(5, nul, t(6, nul, nul)),
 t(9, t(1,nul,nul), t(9,nul,nul)))),T).

为什么答案是5？
提前致谢

Answer 1

q3(t(4,t(2,nul,t(3, t(1,nul,nul), t(9,nul,nul))),t(7, t(5, nul, t(6, nul, nul)), t(9, t(1,nul,nul), t(9,nul,nul)))),T).
    V = 4
    Q1 = t(2,nul,t(3, t(1,nul,nul), t(9,nul,nul)))
        V = 2
        Q1 = nul
        Q2 != nul
    => T1 = 1

    Q2 = t(7, t(5, nul, t(6, nul, nul)), t(9, t(1,nul,nul), t(9,nul,nul)))
        V = 7
        Q1 = t(5, nul, t(6, nul, nul))
            V = 5
            Q1 = nul
            Q2 != nul
        => T1 = 1

        Q2 = t(9, t(1,nul,nul), t(9,nul,nul))
            V = 9
            Q1 = t(1,nul,nul)
            => T1 = 0
            Q2 = t(9,nul,nul)
            => T2 = 0
        => T2 = 1 + 0 + 0 = 1
    => T2 = 1 + 1 + 1 = 3

=> T = 1 + 1 + 3 = 5.

Answer 2

谓词不只是产生 5 作为答案。如果你运行它，它会产生几个答案：5、6、6、6、7、7、6、7 和 7。

结构，t(V, L, R)表示二叉树。重新格式化查询以使其更加可见：

q3( t(4,
         t(2,
             nul,
             t(3,
                  t(1, nul, nul),
                  t(9, nul, nul)
              )
          ),
          t(7,
                t(5,
                     nul,
                     t(6, nul, nul)
                 ),
                t(9,
                     t(1, nul, nul),
                     t(9, nul, nul)
                 )
           )
     ),
  T).

或者，将第一个参数设置得更像 "tree"，这样我们就可以将其可视化：

        _______4_______
       /               \
      2             ____7____
     / \           /         \
    n  _3_        5          _9_
      /   \      / \        /   \
     1     9    n   6      1     9
    / \   / \      / \    / \   / \
   n   n n   n    n   n  n   n n   n

现在让我们考虑由q3定义的规则：

1) q3(t(V, nul, nul), 0).

A node that has no child nodes counts as zero (0). It doesn't count.

2) q3(t(V, Q, nul), 1).
3) q3(t(V, nul, Q), 1).

A node that has at least one nul child counts as 1

4) q3(t(V, Q1, Q2), T) :-
    q3(Q1, T1),
    q3(Q2, T2),
    T is 1+T1+T2.

A node that has two children (regardless of what they are) counts as 1 plus the sum of the quantity given for each the two children.

我们可以从谓词子句的这些定义中看出，任何具有两个 nul 子节点的节点都将满足子句 1、2 或 3。因此，每个这样的节点都可能有助于回溯的 3 个解决方案。但是，谓词 2 和 3 将 "prune" 解决方案低于仅具有一个 nul 子节点的节点。树中只有一个分支没有唯一的 null 子节点，那就是从节点值 9 开始的分支。每个子分支，因为它们有两个 nul 节点，所以提供 3 个解决方案。因此，总共出现了 3x3 或 9 个解决方案，这就是我们所看到的（5、6、6、6、7、7、6、7 和 7）。

判断5是从哪里来的第一个解，只需要看每个节点哪个子句先成功即可。

Node@4: matches rule 4: 1 + Node@2 + Node@7
Node@2: matches rule 3: 1
Node@7: matches rule 4: 1 + Node@5 + Node@9
Node@5: matches rule 3: 1
Node@9: matches rule 4: 1 + Node@1 + Node@9
Node@1: matches rule 1: 0
Node@9: matches rule 1: 0

如果我们将这些相加，我们得到：Node@4 总和为 1 + 1 + 1 + 1 + 1 + 0 + 0 = 5（实际上只是将上面的 1 加起来）。在其他规则也匹配的地方回溯会产生其他 8 个值。

看起来 q3 正在尝试计算节点数，但这样做不正确。为了正确地做到这一点，让我们从定义规则开始：

If a node is nul, it should count as zero

q3(nul, 0).

If a node is not null, then the count of nodes should be the sum of the count of nodes of the left and right branches, plus 1 for the current node

q3(t(_, L, R), C) :- q3(L, CL), q3(R, CR), C is 1 + CL + CR.

使用这两个子句，我们得到：

| ?- q3(t(4,
 t(2,
 nul,
t(3, t(1,nul,nul), t(9,nul,nul))),
 t(7, t(5, nul, t(6, nul, nul)),
 t(9, t(1,nul,nul), t(9,nul,nul)))),T).

T = 11

yes
| ?-

一个解，11，也就是节点数

Answer 3

显而易见的答案是执行以下操作：

?- trace(q3/2), trace(is/2).
%         q3/2: [call,redo,exit,fail]
%         (is)/2: [call,redo,exit,fail]
true.

[debug]  ?- q3(t(4,                   % <- (6)
                 t(2,                 % <- (7)
                   nul,               % (7) -> 1
                   t(3,               % .
                     t(1,nul,nul),    % .
                     t(9,nul,nul))),  % .
                 t(7,                 % <- (7)
                   t(5,               % <- (8)
                     nul,             % (8) -> 1
                     t(6, nul, nul)), % .
                   t(9,               % <- (8)
                     t(1,nul,nul),    % (9) -> 0
                     t(9,nul,nul)     % (9) -> 0
                     )                % 1 + 0 + 0 = 1 (8) -> 1
                    )                 % 1 + 1 + 1 = 3 (7) -> 3
                   ),                 % 1 + 1 + 3 = 5 (6) -> 5
               T).
 T Call: (6) q3(t(4, t(2, nul, t(3, t(1, nul, nul), t(9, nul, nul))), t(7, t(5, nul, t(6, nul, nul)), t(9, t(1, nul, nul), t(9, nul, nul)))), _G386)
 T Call: (7) q3(t(2, nul, t(3, t(1, nul, nul), t(9, nul, nul))), _G538)
 T Exit: (7) q3(t(2, nul, t(3, t(1, nul, nul), t(9, nul, nul))), 1)
 T Call: (7) q3(t(7, t(5, nul, t(6, nul, nul)), t(9, t(1, nul, nul), t(9, nul, nul))), _G538)
 T Call: (8) q3(t(5, nul, t(6, nul, nul)), _G538)
 T Exit: (8) q3(t(5, nul, t(6, nul, nul)), 1)
 T Call: (8) q3(t(9, t(1, nul, nul), t(9, nul, nul)), _G538)
 T Call: (9) q3(t(1, nul, nul), _G538)
 T Exit: (9) q3(t(1, nul, nul), 0)
 T Call: (9) q3(t(9, nul, nul), _G538)
 T Exit: (9) q3(t(9, nul, nul), 0)
 T Call: (9) _G543 is 1+0+0
 T Exit: (9) 1 is 1+0+0
 T Exit: (8) q3(t(9, t(1, nul, nul), t(9, nul, nul)), 1)
 T Call: (8) _G549 is 1+1+1
 T Exit: (8) 3 is 1+1+1
 T Exit: (7) q3(t(7, t(5, nul, t(6, nul, nul)), t(9, t(1, nul, nul), t(9, nul, nul))), 3)
 T Call: (7) _G386 is 1+1+3
 T Exit: (7) 5 is 1+1+3
 T Exit: (6) q3(t(4, t(2, nul, t(3, t(1, nul, nul), t(9, nul, nul))), t(7, t(5, nul, t(6, nul, nul)), t(9, t(1, nul, nul), t(9, nul, nul)))), 5)
T = 5 .

在格式化术语时，查看 q3/2 将用它做什么并不难。谓词足够短，您可以通过肉眼进行模式匹配。但是当然你也可以通过非常详细的跟踪来查看。您会注意到树上的一些子树在第一次搜索解决方案时根本没有被探索过。

我们如何获得该值？

How did we to get that value?

prolog