使用Prolog获取所有可能的二叉树？

Question

我知道有很多关于定义二叉树以检查某些东西是否是二叉树的问题,但我找不到一个在"相反的方向"处理这个问题的线程.

为什么二进制树的定义在被称为"es_arbol(X)"时不会返回所有可能的二叉树？详细解释并尝试实现一个返回所有可能的二叉树结构的不同定义.

好吧,所以基本上我被困在一个任务的这一部分.在定义我的二叉树验证函数后,我注意到当没有参数调用它只返回通过它们的右节点"增长"的树,或者至少是如何我解释swi-prolog的输出.我没有得到的是,假设我的定义是正确的,Prolog应该能够以两种方式构建它们.如果没有,我想如果有人能指出我正确的工作方向找出二叉树的更一般的定义,或者解释为什么我的定义不够.

这是我的定义:

es_arbol(nil).
es_arbol(arbol(_,I,D)) :- es_arbol(I), es_arbol(D).

Answer 1

你的谓词在一个分支上生成无限数量的树的原因是因为你有多个递归,并且像任何语言一样,Prolog将继续进行它找到的第一个递归调用,直到它返回,在这种情况下,永远不会.所以你总是在树的一条腿上递归.换句话说,每个树中至少有两个变量(左右子树),它们具有无限多种可能性.

二叉树沿两个维度具有无限多的递归可能性.您需要一种使用一维度量标准对树进行排序的方法.一个这样的度量可以是树中的节点数.如果按节点计数对树进行排序,从节点计数0开始,则对于每个节点计数,需要枚举有限数量的树.以下是这种方法的一般方法:

1. Nodes 是有效数量的节点
2. nil 是一个有0个节点的有效二叉树
3. arbol(_, TL, TR)是一个有效的二叉树,其中包含N节点if NL和NR2add,N-1并且TL是NL节点TR的有效二叉树,并且是节点的有效二叉树NR.由于Prolog将在该点之前的回溯之前找到来自给定点的所有解,因此它将在回溯到新的有效节点数之前首先搜索具有给定节点数的所有树.

在Prolog中,它看起来像这样.

:- use_module(library(clpfd)).

es_arbol(Tree) :-
    length(_, Nodes),
    es_arbol(Tree, Nodes).

我用length/2"生成" Nodes0,1,2等的值es_arbol(Tree)将成功使用二进制树,连续节点计数从0开始.对于给定的节点计数Nodes,它将es_arbol(Tree, Nodes)在最终失败之前找到所有解决方案.length(_, Nodes)再次回溯到下一个值将成功Node.

es_arbol(nil, 0).
es_arbol(arbol(_,TreeL,TreeR), N) :-
    N #> 0,
    NL + NR #= N - 1,
    NL #>= 0, NR #>= 0,
    es_arbol(TreeL, NL),
    es_arbol(TreeR, NR).

基本案例是微不足道的.nil是具有0个节点的树.递归情况说,这arbol(_,L,R)是一个带有N节点if 的二叉树N > 0,NL并且NR是非负整数加起来N,TL并且TR是分别具有长度NL和的二叉树NR.

运行上面代码的结果是:

?- es_arbol(Tree).
Tree = nil ;
Tree = arbol(_G258, nil, nil) ;
Tree = arbol(_G17, nil, arbol(_G157, nil, nil)) ;
Tree = arbol(_G17, arbol(_G200, nil, nil), nil) ;
Tree = arbol(_G14, nil, arbol(_G154, nil, arbol(_G593, nil, nil))) ;
Tree = arbol(_G14, nil, arbol(_G154, arbol(_G603, nil, nil), nil)) ;
Tree = arbol(_G14, arbol(_G130, nil, nil), arbol(_G191, nil, nil)) ;
Tree = arbol(_G14, arbol(_G53, nil, arbol(_G193, nil, nil)), nil) ;
Tree = arbol(_G14, arbol(_G53, arbol(_G236, nil, nil), nil), nil) ;
Tree = arbol(_G14, nil, arbol(_G100, nil, arbol(_G214, nil, arbol(_G354, nil, nil)))) ;
Tree = arbol(_G14, nil, arbol(_G100, nil, arbol(_G214, arbol(_G397, nil, nil), nil))) ;
Tree = arbol(_G14, nil, arbol(_G100, arbol(_G216, nil, nil), arbol(_G277, nil, nil))) ;
Tree = arbol(_G14, nil, arbol(_G100, arbol(_G139, nil, arbol(_G279, nil, nil)), nil)) ;
Tree = arbol(_G14, nil, arbol(_G100, arbol(_G139, arbol(_G322, nil, nil), nil), nil)) ;
Tree = arbol(_G14, arbol(_G130, nil, nil), arbol(_G191, nil, arbol(_G664, nil, nil))) ;
Tree = arbol(_G14, arbol(_G130, nil, nil), arbol(_G191, arbol(_G674, nil, nil), nil)) ;
Tree = arbol(_G14, arbol(_G132, nil, arbol(_G272, nil, nil)), arbol(_G676, nil, nil)) .
...

正如@false在评论中指出的那样,在应用枚举约束的情况下,使用CLP(FD)并不是最有效的方法.另一种更有效的方法是使用between/3:

es_arbol(nil, 0).
es_arbol(arbol(_,TreeL,TreeR), N) :-
    N > 0,
    N1 is N - 1,
    between(0, N1, NL),
    NR is N1 - NL,
    es_arbol(TreeL, NL),
    es_arbol(TreeR, NR).

Answer 2

Lurker已经使用CLP(FD)约束给出了非常好的通用解决方案.

我想用一种限制搜索深度的替代方法来扩充现有答案.我使用列表以符号方式"计数" 而不是整数.

为了推理Prolog中的列表,DCG表示法(dcg)通常非常方便,在这种情况下:

es_arbol(nil) --> [].
es_arbol(arbol(_,I,D)) --> [_], es_arbol(I), es_arbol(D).

在声明中,您可以将这些规则视为"消费信贷"来应用.

如果我天真地查询,那么我得到一个不公平的枚举:

?- phrase(es_arbol(A), Ls).
A = nil,
Ls = [] ;
A = arbol(_9016, nil, nil),
Ls = [_9024] ;
A = arbol(_9016, nil, arbol(_9030, nil, nil)),
Ls = [_9024, _9038] ;
A = arbol(_9016, nil, arbol(_9030, nil, arbol(_9044, nil, nil))),
Ls = [_9024, _9038, _9052] ;
A = arbol(_9016, nil, arbol(_9030, nil, arbol(_9044, nil, arbol(_9058, nil, nil)))),
Ls = [_9024, _9038, _9052, _9066] .

关键是我们可以通过限制列表的长度轻松将其转换为公平的枚举.例如,要获得具有两个内部节点的所有树,我们可以使用:

?- phrase(es_arbol(A), [_,_]).
A = arbol(_10426, nil, arbol(_10434, nil, nil)) ;
A = arbol(_10426, arbol(_10434, nil, nil), nil) ;
false.

在此基础上,我们可以使用迭代深化来公平地枚举所有树形状:

?- length(Ls, _), phrase(es_arbol(A), Ls).
Ls = [],
A = nil ;
Ls = [_7130],
A = arbol(_7142, nil, nil) ;
Ls = [_7130, _7136],
A = arbol(_7148, nil, arbol(_7156, nil, nil)) ;
Ls = [_7130, _7136],
A = arbol(_7148, arbol(_7156, nil, nil), nil) ;
Ls = [_7130, _7136, _7142],
A = arbol(_7154, nil, arbol(_7162, nil, arbol(_7170, nil, nil))) ;
Ls = [_7130, _7136, _7142],
A = arbol(_7154, nil, arbol(_7162, arbol(_7170, nil, nil), nil)) ;
Ls = [_7130, _7136, _7142],
A = arbol(_7154, arbol(_7162, nil, nil), arbol(_7170, nil, nil)) .

因此,"象征性地"计数有时是使用实际整数的方便替代.