数学序言 - 在序言中搜索节点级别

Question

假设这里是一个二叉搜索树，并且给定规则 above(X,Y) - X 在 Y 的正上方。我还创建了规则 root(X) - X 没有父项。

然后，我试图弄清楚这棵树中节点的深度。假设树的根节点是"r" 所以我得到了事实level(r,0)。为了实现规则level(N,D) :-，我在想应该在这里进行递归。因此，我尝试了

level(N,D): \+ root(N), above(X,N), D is D+1, level(X,D).

所以如果N不是根，在N上面有节点X，层D加一，然后递归。但是当我测试这个时，它只适用于根条件。当我创建更多事实时，例如节点 "s" 是节点 "r" 的左子节点，我的查询是 level(s,D)。它returns我"no"。我跟踪查询，它显示

  1    1  Call: level(s,_16) ? 
  1    1  Fail: level(s,_16) ?

我只是困惑为什么我调用 level(s,D) 时它会失败？

Answer 1

您的查询有一些问题：

在Prolog中你不能写D is D+1这样的东西，因为一个变量只能赋一个值；
在你调用D is D+1的时候，D还没有实例化，所以可能会出错；和
您从未声明（至少在可见代码中没有）根的 level/2 是 0。

一个解决方案是首先说明任何根的水平是0:

level(N,0) :-
    root(N).

现在我们必须定义归纳情况：首先我们确实使用 above/2 谓词查找父项。执行 N 不是 root/1 的检查严格来说是没有必要的，因为它会与存在 above/2 的事实相冲突。接下来我们确定该父级 LP 的级别，最后我们通过声明 L is LP+1 计算我们节点的级别，其中 L 是 N 和 [=24= 的级别] 级别操作 P:

level(N,L) :-
    above(P,N),
    level(P,LP),
    L is LP+1.

或者把它们放在一起：

level(N,0) :-
    root(N).
level(N,L) :-
    above(P,N),
    level(P,LP),
    L is LP+1.

由于您没有提供示例树，我无法测试该谓词是否按您预期的方式运行。

关于root/1

请注意，通过编写 root/1，您引入了数据重复：您可以简单地编写：

root(R) :-
    \+ above(_,R).

数学序言 - 在序言中搜索节点级别

prolog in math - searching the level of node in prolog

math

logic

prolog

prolog-toplevel