我正在使用 GNU Prolog。如果我问：
| ?- X #= Y+1, Y #< 4, Y #\= 2.
我得到：
X = _#20(1..4)
Y = _#3(0..1:3)
但是，由于 Y!=2 和 X=Y+1，我也期望 X!=3。
这种行为是由于什么原因造成的？
问问题
92 次
1 回答
2
整数约束求解通过为每个变量维护一个域（一组可能值）来工作。添加约束时，一致性算法负责通过删除一些不可能的值来更新所涉及变量的域。实际上，删除所有不可能的值（因此实际上是不可能的）成本太高。因此，有几种一致性技术，它们的精确程度不同（它们越精确，执行时间就越长）。
通常，对于方程，仅更新域的边界（下限值和上限值）（这称为边界一致性）。在您的示例中就是这种情况X #= Y+1。添加时Y #\= 2，Y 的域被修改（删除 2），但由于这既不会改变其下限 (0) 也不会改变其上限 (3)，因此不会重新考虑 X 的域。因此，您获得的域：
X = _#20(1..4)
Y = _#3(0..1:3)
因此，域是近似值：实际解决方案仅包含域中的值，但并非域的所有值都是解决方案的一部分。从正确性的角度来看，这不是问题，因为最后，搜索阶段（也称为标记）将通过尝试域中的剩余值来发现解决方案。如果一个不可能的值仍然存在，它将导致失败，并且将尝试另一个值（请参阅fd_labeling）。
最后，在 gprolog 下，您可以要求一个更精确的一致性算法（称为域一致性/ arc-consistency），其中所有值都被一一测试。为此我们使用X #=# Y+1，我们可以看到 3 已从 X 的域中删除。
| ?- X #=# Y+1, Y #< 4, Y #\= 2.
X = _#20(1..2:4)
Y = _#3(0..1:3)
显然，这在执行时间方面更加昂贵。另一方面，它将避免在标记时测试更多不可能的值。
于 2021-05-08T08:37:32.103 回答