recursion - Prolog 树中给定深度的节点数

Question

我是 Prolog 的新手。我正在尝试编写一个谓词，该谓词返回树中给定深度的 二叉树 的节点数。比如下面这棵树

有1个深度为0的节点(根节点)，2个深度为1的节点，3个深度为2的节点和3个深度为3的节点。

在我的程序中，二叉树表示为 [value, left-child, right-child] 形式的列表，其中左右子节点本身可以​​用相同的方式表示。例如，这是上面树的表示:

[8, [3, [1, [], []], 
        [6, [4, [], []], 
            [7, [], []]]], 
    [10, [], 
         [14, 
            [13, [], []], 
            []]]]

这是我到目前为止的想法:

nbNodes([_,_,_],1,0).
nbNodes([_,LC,RC],N2,D2) :- 
    nbNodes(LC,NL,D), nbNodes(RC,NR,D), N2 is NL+NR, D2 is D+1.

基于我对 Prolog 的有限理解，这意味着:

1. 每棵树只有一个深度为0的节点。
2. 一棵树中深度为D2的节点数是三者的左右子节点中深度为D2-1的节点数之和。
   
   这两个假设似乎都是正确的。

但是，当我测试我的代码时，返回的数字(如果有的话)是错误的。例如，以下代码输出“false”而不是“3”:

nbNodes([8, [3, [1, [], []], [6, [4, [], []], [7, [], []]]], [10, [], [14, [13, [], []], []]]], N, 2).

我做错了什么？非常感谢。

Answer 1

怎么样

nbNodes( [],0,_).
nbNodes( [_,_,_],1,0).
nbNodes( [_,LC,RC],N2,D2):-
    D2 > 0,
    D is D2-1,
    nbNodes( LC,NL,D), 
    nbNodes( RC,NR,D), 
    N2 is NL+NR.

结果是:

?- T = [8,[3,[1,[],[]],[6,[4,[],[]],[7,[],[]]]],[10,[],[14,[13,[],[]],[]]]],
   nbNodes(T,N,0).
T = [8, [3, [1, [], []], [6, [4, []|...], [7|...]]], [10, [], [14, [13|...], []]]],
N = 1 ;
false.
    
?- T = [8,[3,[1,[],[]],[6,[4,[],[]],[7,[],[]]]],[10,[],[14,[13,[],[]],[]]]],
   nbNodes(T,N,1).
T = [8, [3, [1, [], []], [6, [4, []|...], [7|...]]], [10, [], [14, [13|...], []]]],
N = 2 ;
false.
    
?- T = [8,[3,[1,[],[]],[6,[4,[],[]],[7,[],[]]]],[10,[],[14,[13,[],[]],[]]]],
   nbNodes(T,N,2).
T = [8, [3, [1, [], []], [6, [4, []|...], [7|...]]], [10, [], [14, [13|...], []]]],
N = 3 ;
false.
    
?- T = [8,[3,[1,[],[]],[6,[4,[],[]],[7,[],[]]]],[10,[],[14,[13,[],[]],[]]]],
   nbNodes(T,N,3).
T = [8, [3, [1, [], []], [6, [4, []|...], [7|...]]], [10, [], [14, [13|...], []]]],
N = 3 ;
false.

?- T = [8,[3,[1,[],[]],[6,[4,[],[]],[7,[],[]]]],[10,[],[14,[13,[],[]],[]]]], 
   nbNodes(T,N,4).
T = [8, [3, [1, [], []], [6, [4, []|...], [7|...]]], [10, [], [14, [13|...], []]]],
N = 0.

两个主要的变化是

1. 我为空二叉树添加了一个子句。
2. 我从 D2 计算了 D，之前 我再次调用谓词并且不从 D2 计算 D 在递归调用之后。

我猜你是在问有什么区别，因为你被告知 Prolog 是声明性的，因此我们只需要指定情况(我们的知识库)，而不是如何从我们的知识中推断出某些东西。

好吧，你被骗了。 Prolog 不是纯粹的声明性的，因为有一个顺序，它在其中搜索答案。

如果你想通过使用子句来证明目标G

G :- L1,L2,L3.

Prolog 试图证明 L1，然后是 L2，然后是 L3 - 虽然从逻辑的角度来看，这个子句什么也没说，但是

IF L1 and L2 and L3 THEN G,

逻辑上等同于

IF L3 and L1 and L2 THEN G

如果 Prolog 检查了所有可能的订单，可能会有证据，但它没有。

此外，对于许多谓词，某些参数需要实例化才能使谓词起作用。其中一个谓词是 is/2。它的右侧需要完全实例化，is/2 才能工作。

您的谓词需要实例化其第三个参数。你打电话时nbNodes(LC,NL,D) 和 nbNodes(RC,NR,D)，D 没有实例化。即使您更改了子句的顺序并将 D2 is D+1 放在这些子句之前，这也不起作用，因为 is/2 需要其右侧来被完全实例化，而 D 在那个时候还没有被实例化。

尝试询问 ?- X is 2。和 ?- 2 是 X。 看看区别。

要获得更全面的了解，您需要深入研究 Prolog 对解析原则 的(部分)实现。如果您想拥有更具声明性的 Prolog，请查看约束逻辑编程。