6

作为一个基本的 Prolog 练习，我为自己设定了编写一个可以向前和“向后”工作的二叉树高度谓词的任务——也就是说，除了确定已知二叉树的高度外，它应该能够找到所有二叉树已知高度的树木（包括不平衡的树木）。这是迄今为止我想出的最好的解决方案......

tree_eq1([],s).  % Previously had a cut here - removed (see comments for reason)
tree_eq1([_|T],n(L,R)) :- tree_eq1(T,L), tree_eq1(T,R).
tree_eq1([_|T],n(L,R)) :- tree_eq1(T,L), tree_lt1(T,R).
tree_eq1([_|T],n(L,R)) :- tree_lt1(T,L), tree_eq1(T,R).

tree_lt1([_|_],s).
tree_lt1([_,X|T],n(L,R)) :- XX=[X|T], tree_lt1(XX,L), tree_lt1(XX,R).

第一个参数是高度，表示为一个列表 - 元素无关紧要，列表的长度表示树的高度。所以我基本上是在滥用列表作为 Peano 风格的自然数。方便的原因是...

  1. 不用担心负数。
  2. 我可以在不知道确切数字的情况下检查 > 或 >= - 例如，通过匹配列表头部的两个项目，我确保列表长度 >=2 而无需关心尾部的长度。

这些属性似乎都不适用于 Prolog 数字，到目前为止，我想不出一种方法来采用相同的基本方法来使用实际数字来代替这些列表。

我在 Prolog 中看到了一些使用 Peano 风格数字的例子，所以我的问题是 - 这是正常的做法吗？或者有什么方法可以避免我还没有发现的问题？

此外，有没有一种方法可以转换为/从不会破坏双向性的 Peano 风格的表示？由于相当明显的原因，以下内容不起作用......

length(L,N), tree_eq1(L,X).
  % infinite set of lists to explore if N is unknown

tree_eq1(L,X), length(L,N)
  % infinite set of trees to explore if X is unknown

到目前为止，我能想到的最好的方法是在实现之间进行选择的 is-this-variable-instantiated 测试，这对我来说似乎是在欺骗。

顺便说一句 - 我对其他方法有一些想法，我不想剧透 - 特别是一种动态编程方法。我真的专注于充分理解这次特殊尝试的教训。

4

1 回答 1

5

首先：+1 用于使用列表长度进行计数，这有时确实非常方便，并且是后继符号的一个很好的替代方案。

第二：对于可逆算术，您通常使用约束而不是后继符号，因为约束允许您使用实际数字并带有数字之间通常数学关系的内置定义。

例如，使用 SICStus Prolog 或 SWI：

:- use_module(library(clpfd)).

tree_height(s, 0).
tree_height(n(Left,Right), Height) :-
        Height #>= 0,
        Height #= max(HLeft,HRight) + 1,
        tree_height(Left, HLeft),
        tree_height(Right, HRight).

示例查询：

?- tree_height(Tree, 2).
Tree = n(s, n(s, s)) ;
Tree = n(n(s, s), s) ;
Tree = n(n(s, s), n(s, s)) ;
false.

第三，请注意，最通用的查询 ,?- tree_eq1(X, Y).在您的版本中不能令人满意地工作。使用上面的代码片段，至少它提供了无限数量的解决方案（应该如此）：

?- tree_height(T, H).
T = s,
H = 0 ;
T = n(s, s),
H = 1 ;
T = n(s, n(s, s)),
H = 2 .

我把他们的公平列举作为练习。

于 2014-09-22T05:47:20.387 回答