Prolog 中方程组的意外结果
Unexpected result with a system of (in)equations in Prolog
我正在使用 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。
这种行为是由于什么造成的？
通过为每个变量维护一个 domain（可能值的集合）来求解整数的约束。添加约束后，一致性算法负责通过删除 some 不可能的值来更新所涉及变量的域。事实上，删除 all 不可能的值（因此实际上是不可能的）的成本太高了。因此，有几种一致性技术在它们的精确度上有所不同（它们越精确，它们执行的时间就越长）。
一般来说，对于方程，只有 边界 域（下限值和上限值）被更新（这称为 边界一致性 ). X #= Y+1 示例中就是这种情况。添加 Y #\= 2 时，Y 的域被修改（删除 2），但由于这既不改变其下限 (0) 也不改变其上限 (3)，因此不会重新考虑 X 的域。因此您获得的域：
X = _#20(1..4)
Y = _#3(0..1:3)
域因此是一个近似值：实际解决方案仅包含域中的值，但并非域的所有值都是解决方案的一部分。从正确性的角度来看，这不是问题，因为最后，搜索阶段（也称为标记）将通过尝试域中的剩余值来发现解决方案。如果一个不可能的值仍然存在，它将导致失败并尝试另一个值（参见 fd_labeling）。
最后，在gprolog下，你可以要求更精确的一致性算法（称为domain consistency / arc-consistency），其中所有值一一测试。为此，我们使用 X #=# Y+1，我们可以看到 3 已从 X 的域中删除。
| ?- X #=# Y+1, Y #< 4, Y #\= 2.
X = _#20(1..2:4)
Y = _#3(0..1:3)
显然，这在执行时间方面更昂贵。另一方面，它将避免在标记时测试更多不可能的值。
我正在使用 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。
这种行为是由于什么造成的？
通过为每个变量维护一个 domain（可能值的集合）来求解整数的约束。添加约束后，一致性算法负责通过删除 some 不可能的值来更新所涉及变量的域。事实上，删除 all 不可能的值（因此实际上是不可能的）的成本太高了。因此，有几种一致性技术在它们的精确度上有所不同（它们越精确，它们执行的时间就越长）。
一般来说，对于方程，只有 边界 域（下限值和上限值）被更新（这称为 边界一致性 ). X #= Y+1 示例中就是这种情况。添加 Y #\= 2 时，Y 的域被修改（删除 2），但由于这既不改变其下限 (0) 也不改变其上限 (3)，因此不会重新考虑 X 的域。因此您获得的域：
X = _#20(1..4)
Y = _#3(0..1:3)
域因此是一个近似值：实际解决方案仅包含域中的值，但并非域的所有值都是解决方案的一部分。从正确性的角度来看，这不是问题，因为最后，搜索阶段（也称为标记）将通过尝试域中的剩余值来发现解决方案。如果一个不可能的值仍然存在，它将导致失败并尝试另一个值（参见 fd_labeling）。
最后，在gprolog下，你可以要求更精确的一致性算法（称为domain consistency / arc-consistency），其中所有值一一测试。为此，我们使用 X #=# Y+1，我们可以看到 3 已从 X 的域中删除。
| ?- X #=# Y+1, Y #< 4, Y #\= 2.
X = _#20(1..2:4)
Y = _#3(0..1:3)
显然，这在执行时间方面更昂贵。另一方面，它将避免在标记时测试更多不可能的值。