我们是怎么得到这个价值的？

Question

让我们考虑一下给定的数据库：

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

或者，让第一个论点更像一棵“树”，这样我们就可以将它可视化：

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

没有子节点的节点计算为零(0)。这不算数。

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

具有至少一个nul子节点的节点可计算为1。

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

有两个子节点(不管它们是什么)的节点计算为1加上每个子节点的数量之和。

从这些谓词子句的定义中可以看出，任何有两个nul子节点都会满足子句1、2或3的要求，因此每个节点都有可能提供3种回溯解决方案。但是，谓词2和3将“修剪”节点以下的解决方案，这些节点只有一个nul子节点。树中只有一个分支没有唯一的一个空子，那就是以节点值9开始的分支。每个子分支，因为它们有两个nul节点，贡献了3种解决方案。这是3x3或9的总解决方案，这就是我们所看到的(5，6，6，6，7，7，6，7，7，7，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+0+0=5(实际上只是计算上面的1's )。回溯，其中其他规则也将匹配产生其他8个值。

​

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

​

如果节点为nul，则应将其计算为零。

q3(nul, 0).

如果一个节点不是空的，那么节点的计数应该是左、右分支节点数的总和，加上当前节点的1。

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将使用它做什么并不太困难。谓词足够短，您可以通过眼睛进行模式匹配。当然，您也可以查看非常详细的跟踪。您将注意到在树上，一些子树在第一次搜索解决方案时根本没有被探索过。