Prolog中tree_order查询回溯时陷入无限循环的解决方法咨询

问题原因 #

你遇到的无限循环是两个原因共同导致的：

• 没有给左右子树的节点数添加非负约束，CLP(FD)的整数变量默认允许取负值，回溯时会生成超出范围的节点数组合
• 递归调用前没有将子树节点数变量实例化为固定数值，Prolog会无限尝试生成更大的左子树，哪怕对应右子树节点数已经为负、不可能存在有效解

解决方法 #

方法1：调整CLP(FD)约束顺序，增加数值范围限定

首先确保导入CLP(FD)库，给子树节点数加非负约束，递归前用labeling实例化节点数变量，从根源上避免无效的递归尝试：

% 导入CLP(FD)库，SWI-Prolog等大部分实现默认需要手动导入
:- use_module(library(clpfd)).

% 修正后的树节点数计算谓词
tree_order(empty,0).
tree_order(tree(_, Left_Subtree, Right_Subtree), Order) :- 
    Order #> 0,
    % 新增：子树节点数非负约束
    Left_Subtree_Order #>= 0,
    Right_Subtree_Order #>= 0,
    Order #= Left_Subtree_Order + Right_Subtree_Order + 1,
    % 新增：递归前先实例化两个子树的节点数，范围已经被上面的约束限定死
    labeling([ff], [Left_Subtree_Order, Right_Subtree_Order]),
    tree_order(Left_Subtree, Left_Subtree_Order), 
    tree_order(Right_Subtree, Right_Subtree_Order).

查询tree_order(Tree, 2).会得到两个有效解后直接终止，不会进入循环。

方法2：不用CLP，用原生算术限定范围

如果你不想用CLP，也可以用between直接限定子树节点数的取值范围，递归前就固定子树大小：

tree_order(empty, 0).
tree_order(tree(_, Left_Subtree, Right_Subtree), Order) :-
    Order > 0,
    SubTotal is Order - 1,
    % 直接限定左子树节点数的取值范围，不会生成超出上限的值
    between(0, SubTotal, Left_Order),
    Right_Order is SubTotal - Left_Order,
    tree_order(Left_Subtree, Left_Order),
    tree_order(Right_Subtree, Right_Order).

内容的提问来源于stack exchange，提问作者Luiz