prolog - 大多数通用查询仅在 Learn Prolog Now 的 Exercize 3.5 中为树 N 的每个叶子数找到一个解决方案

Question

所以在这里查看练习 3.5 的描述：

%%  Exercise  3.5 %%

%  Binary trees are trees where all internal nodes have exactly two children. 
%  The smallest binary trees consist of only one leaf node. We will represent leaf nodes as 
%  leaf(Label) . For instance, leaf(3) and leaf(7) are leaf nodes, and therefore small binary 
%  trees. Given two binary trees B1 and B2 we can combine them into one binary tree using the 
%  functor tree/2 as follows: tree(B1,B2) . So, from the leaves leaf(1) and leaf(2) we can build
%  the binary tree tree(leaf(1),leaf(2)) . And from the binary trees tree(leaf(1),leaf(2)) and 
%  leaf(4) we can build the binary tree tree(tree(leaf(1),  leaf(2)),leaf(4)).

% Now, define a predicate swap/2 , which produces the mirror image of the binary tree that is its first argument. For example:

%    ?-  swap(tree(tree(leaf(1),  leaf(2)),  leaf(4)),T).
%    T  =  tree(leaf(4),  tree(leaf(2),  leaf(1))).
%    yes

这是我的实现：

swap(tree(leaf(X), leaf(Y)), tree(leaf(Y), leaf(X))).
swap(tree(B1, leaf(Y)), tree(leaf(Y), SwapB1)) :- 
    dif(B1, leaf(_)),
    swap(B1, SwapB1).
swap(tree(leaf(X), B2), tree(SwapB2, leaf(X))) :- 
    dif(B2, leaf(_)),
    swap(B2, SwapB2).
swap(tree(B1, B2), tree(B2,B1)) :- 
    dif(B1, leaf(_)),
    dif(B2, leaf(_)).

当我执行以下查询时swap(T1,T).，我得到：

?- swap(T1,T).
T1 = tree(leaf(_A), leaf(_B)),
T = tree(leaf(_B), leaf(_A)) ;
T1 = tree(tree(leaf(_A), leaf(_B)), leaf(_C)),
T = tree(leaf(_C), tree(leaf(_B), leaf(_A))) ;
T1 = tree(tree(tree(leaf(_A), leaf(_B)), leaf(_C)), leaf(_D)),
T = tree(leaf(_D), tree(leaf(_C), tree(leaf(_B), leaf(_A)))) ;
T1 = tree(tree(tree(tree(leaf(_A), leaf(_B)), leaf(_C)), leaf(_D)), leaf(_E)),
T = tree(leaf(_E), tree(leaf(_D), tree(leaf(_C), tree(leaf(_B), leaf(_A))))) .

正如你所看到的，Prolog 没有考虑每个叶子 N 数的所有解决方案。例如，对于 N = 4，T1 = tree( tree(leaf(_A) , leaf(_B)), tree(leaf(_C), leaf(_D)) )没有考虑这种情况。

编辑：将案例 N=3 更改为 N=4，现在我认为它更清楚了。

我试图让 Prolog 考虑树的每个叶子 N 数量的所有解决方案，而不依赖用户 @ false之前建议的 CLPFD

感谢您的关注！

标签： prolog

Answer 1

您的问题称为枚举的公平性。Prolog 的回溯算法尽可能深入地探索目标中的最后一个递归调用，因此如果一个目标中有两个递归调用，枚举总是会“卡在”第二个中。

这是一个更简单的例子，只是枚举树：

tree(leaf(_)).
tree(tree(Left, Right)) :-
    tree(Left),
    tree(Right).

就像您的情况一样，这会构建向右加深的树：

?- tree(Tree).
Tree = leaf(_1986) ;
Tree = tree(leaf(_1992), leaf(_1996)) ;
Tree = tree(leaf(_1992), tree(leaf(_2002), leaf(_2006))) ;
Tree = tree(leaf(_1992), tree(leaf(_2002), tree(leaf(_2012), leaf(_2016)))) ;
Tree = tree(leaf(_1992), tree(leaf(_2002), tree(leaf(_2012), tree(leaf(_2022), leaf(_2026))))) .

解决此问题的方法是引入某种“大小”度量，例如叶子的数量，并以大小为指导进行枚举。这就是为什么建议使用 CLPFD 算法的原因。如果没有算术，一种方法是使用列表。

这是一个关联树及其叶子列表的谓词：

tree_leaves(leaf(X), [X]).
tree_leaves(tree(Left, Right), Leaves) :-
    LeftLeaves = [_ | _],
    RightLeaves = [_ | _],
    append(LeftLeaves, RightLeaves, Leaves),
    tree_leaves(Left, LeftLeaves),
    tree_leaves(Right, RightLeaves).

例如：

?- Leaves = [a, b, c], tree_leaves(Tree, Leaves).
Leaves = [a, b, c],
Tree = tree(leaf(a), tree(leaf(b), leaf(c))) ;
Leaves = [a, b, c],
Tree = tree(tree(leaf(a), leaf(b)), leaf(c)) ;
false.

如您所见，对于固定长度的列表，这确实枚举了所有（两个）可能的树结构。

所以现在我们想做一些类似的事情，公平地枚举所有固定长度的列表——这将强制公平地枚举相应的树。可以使用length/2谓词公平地枚举列表：

?- length(List, N).
List = [],
N = 0 ;
List = [_2242],
N = 1 ;
List = [_2242, _2248],
N = 2 ;
List = [_2242, _2248, _2254],
N = 3 ;
List = [_2242, _2248, _2254, _2260],
N = 4 .

所以：

?- length(Leaves, N), tree_leaves(Tree, Leaves).
Leaves = [_2798],
N = 1,
Tree = leaf(_2798) ;
Leaves = [_2798, _2804],
N = 2,
Tree = tree(leaf(_2798), leaf(_2804)) ;
Leaves = [_2798, _2804, _2810],
N = 3,
Tree = tree(leaf(_2798), tree(leaf(_2804), leaf(_2810))) ;
Leaves = [_2798, _2804, _2810],
N = 3,
Tree = tree(tree(leaf(_2798), leaf(_2804)), leaf(_2810)) ;
Leaves = [_2798, _2804, _2810, _2816],
N = 4,
Tree = tree(leaf(_2798), tree(leaf(_2804), tree(leaf(_2810), leaf(_2816)))) ;
Leaves = [_2798, _2804, _2810, _2816],
N = 4,
Tree = tree(leaf(_2798), tree(tree(leaf(_2804), leaf(_2810)), leaf(_2816))) ;
Leaves = [_2798, _2804, _2810, _2816],
N = 4,
Tree = tree(tree(leaf(_2798), leaf(_2804)), tree(leaf(_2810), leaf(_2816))) ;
Leaves = [_2798, _2804, _2810, _2816],
N = 4,
Tree = tree(tree(leaf(_2798), tree(leaf(_2804), leaf(_2810))), leaf(_2816)) ;
Leaves = [_2798, _2804, _2810, _2816],
N = 4,
Tree = tree(tree(tree(leaf(_2798), leaf(_2804)), leaf(_2810)), leaf(_2816)) ;
Leaves = [_2798, _2804, _2810, _2816, _2822],
N = 5,
Tree = tree(leaf(_2798), tree(leaf(_2804), tree(leaf(_2810), tree(leaf(_2816), leaf(_2822))))) .

我们可以把它打包：

fairtree(Tree) :-
    length(Leaves, _N),
    tree_leaves(Tree, Leaves).

swap/2然后用公平的枚举测试你的谓词：

?- fairtree(Tree), swap(Tree, Swapped).
Tree = tree(leaf(_2122), leaf(_2128)),
Swapped = tree(leaf(_2128), leaf(_2122)) ;
Tree = tree(leaf(_2874), leaf(_2878)),
Swapped = tree(leaf(_2878), leaf(_2874)),
dif(_2906, _2874),
dif(_2918, _2878) ;
Tree = tree(leaf(_2122), tree(leaf(_2128), leaf(_2134))),
Swapped = tree(tree(leaf(_2134), leaf(_2128)), leaf(_2122)) ;
Tree = tree(leaf(_2922), tree(leaf(_2932), leaf(_2936))),
Swapped = tree(tree(leaf(_2936), leaf(_2932)), leaf(_2922)),
dif(_2974, _2932),
dif(_2986, _2936) ;
Tree = tree(leaf(_2690), tree(leaf(_2700), leaf(_2704))),
Swapped = tree(tree(leaf(_2700), leaf(_2704)), leaf(_2690)),
dif(_2732, _2690) ;
Tree = tree(tree(leaf(_2122), leaf(_2128)), leaf(_2134)),
Swapped = tree(leaf(_2134), tree(leaf(_2128), leaf(_2122))) ;
Tree = tree(tree(leaf(_2934), leaf(_2938)), leaf(_2942)),
Swapped = tree(leaf(_2942), tree(leaf(_2938), leaf(_2934))),
dif(_2980, _2934),
dif(_2992, _2938) ;
Tree = tree(tree(leaf(_2702), leaf(_2706)), leaf(_2710)),
Swapped = tree(leaf(_2710), tree(leaf(_2702), leaf(_2706))),
dif(_2738, _2710) ;
Tree = tree(leaf(_2122), tree(leaf(_2128), tree(leaf(_2134), leaf(_2140)))),
Swapped = tree(tree(tree(leaf(_2140), leaf(_2134)), leaf(_2128)), leaf(_2122)) ;
Tree = tree(leaf(_2970), tree(leaf(_2980), tree(leaf(_2990), leaf(_2994)))),
Swapped = tree(tree(tree(leaf(_2994), leaf(_2990)), leaf(_2980)), leaf(_2970)),
dif(_3042, _2990),
dif(_3054, _2994) ;
Tree = tree(leaf(_2738), tree(leaf(_2748), tree(leaf(_2758), leaf(_2762)))),
Swapped = tree(tree(tree(leaf(_2758), leaf(_2762)), leaf(_2748)), leaf(_2738)),
dif(_2800, _2748) ;
Tree = tree(leaf(_2724), tree(leaf(_2734), tree(leaf(_2744), leaf(_2748)))),
Swapped = tree(tree(leaf(_2734), tree(leaf(_2744), leaf(_2748))), leaf(_2724)),
dif(_2776, _2724) .

（无论如何，规范的定义swap比你的更短更简单。两个子句就足够了。）