树方法进行无限循环 [英] Tree methods going on infinite loop

问题描述

所以当我实例化我的整数变量时，我所有的树代码都不能正常工作.这是我的意思的一个例子:

So all of my tree code is not working properly when I instantiate my integer variables. Here's an example of what I mean:

% relates a tree and the numbe of nodes in that tree(order)
tree_order(empty,0).
tree_order(tree(_, Left_Subtree, Right_Subtree), Order) :- 
    Order #> 0,
    Order #= Left_Subtree_Order + Right_Subtree_Order + 1,
    tree_order(Left_Subtree, Left_Subtree_Order), tree_order(Right_Subtree, Right_Subtree_Order).

我实际上并没有使用它，但这是我对树的定义:

I'm not actually using that but here's my definition of a tree:

% Definition of a Binary Tree

tree(empty).
tree(tree(_, Left_Subtree, Right_Subtree)) :- 
    tree(Left_Subtree), tree(Right_Subtree).

因此，如果运行以下查询 tree_order(Tree, 2). 它会给我一个解决方案，然后当它回溯时它会进入无限循环.老实说，这让我感到困惑，因为我已经在脑海中运行了该程序一千次，但仍然找不到答案.

So if run the following query tree_order(Tree, 2). it gives me a solution then when it backtracks it goes on an infinite loop. It's honestly baffling me, because I've run the program in my head a thousand times and I still can't find an answer.

一种可能性是 Prolog 在树的左侧添加了无数个节点，但它没有意识到它实际上导致树的阶数大于 2.

One possibility is that Prolog is adding infinitely many nodes to the left of the tree and it doesn't realize that it actually leads to the tree having order greater than 2.

但如果是这种情况，我如何告诉 prolog 停止向树中添加超过 2 个节点?我曾考虑过使用 CLP，但我知道的唯一方法是关于数字域和列表而不是谓词.

But if that's the case, how can I tell prolog to stop adding more than 2 nodes to the tree? I've thought about using CLP but the only methods I know reason about numerical domains and lists but not predicates.

提前致谢！

推荐答案

更好地约束每个自由的变量:

/*  File:    tree_order.pl
    Author:  Carlo,,,
    Created: Oct 19 2021
    Purpose: https://stackoverflow.com/q/69623834/874024
*/

:- module(tree_order,
          [tree_order/2
          ]).
:- use_module(library(clpfd)).

% relates a tree and the number of nodes in that tree(order)
tree_order(empty, 0).
tree_order(tree(_, Left_Subtree, Right_Subtree), Order) :-
    % Order #> 0, implicit given the following 3 constraints
    Left_Subtree_Order #>= 0,
    Right_Subtree_Order #>= 0,
    Order #= Left_Subtree_Order + Right_Subtree_Order + 1,
    tree_order(Left_Subtree, Left_Subtree_Order),
    tree_order(Right_Subtree, Right_Subtree_Order).

产量

[debug]  ?- tree_order(T,2).
T = tree(_, empty, tree(_, empty, empty)) ;
T = tree(_, tree(_, empty, empty), empty) ;
false.

这篇关于树方法进行无限循环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！