prolog - Prolog 中方程组的意外结果

Question

我正在使用 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。

这种行为是由于什么造成的？

Answer 1

通过为每个变量维护一个域(可能值的集合)来对整数进行约束求解。添加约束后，一致性算法负责通过删除一些不可能的值来更新相关变量的域。事实上，移除所有 不可能的值(因此实际上是不可能的)的代价太大。因此，有几种一致性技术在精确度上有所不同(它们越精确，执行所需的时间就越长)。

通常，对于方程式，只有域的边界(下限值和上限值)会更新(这称为边界一致性)。在您使用 X #= Y+1 的示例中就是这种情况。添加 Y #\= 2 时，Y 的域被修改(删除 2)，但由于这既不改变它的下限 (0) 也不改变它的上限 (3)，因此 Y 的域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)

显然，这在执行时间方面更昂贵。另一方面，它将避免在标记时测试更多不可能的值。