什么是边界传播

Question

我试图弄清楚clpfd中的边界传播是什么，但似乎在任何地方都找不到很好的解释。

我正在为 Prolog 和 clpfd 进行修改并遇到了这个问题，但查看讲义对我来说没有意义。有人可以解释一下边界传播的实际含义及其用途吗？

这是我所指的问题：

当以下Prolog程序

:- use_module(library(clpfd)).
bounds(X, Y, Z) :-
X in 1..5,
Y in 1..2,
Z in 3..5,
X #= Y + Z.

被查询时，它给出了答案：

?- bounds(X, Y, Z).
X in 4..5,
Y in 1..2,
Z in 3..4.

解释如何应用边界传播来推断此答案。

Answer 1

边界传播是约束求解器自动应用 的一种传播形式。对于用户来说，关键点是他们不需要了解其背后的算法，而是可以简单地依靠约束求解器为他们完成 工作。在您显示的结果中，求解器已应用了这种传播形式。

要了解约束求解器为您做什么，请从以下开始：

我们知道：

• Y至少为1
• Z至少为3
• X是Y和Z的总和。

因此(练习：为什么？)：X至少是4。

然后，对所有其他变量重复此推理，包括上限和下限！

重复此操作，直到无法从任何变量中删除更多的域元素，这称为传播的固定 点。完成此操作后，您已经建立了边界 一致性。