SWI Prolog 与 GNU Prolog - SWI 下的 CLP(FD) 问题
SWI Prolog vs. GNU Prolog - CLP(FD) issues under SWI
我在 Prolog 中写了一个快速谓词来试用 CLP(FD) 及其求解方程组的能力。
problem(A, B) :-
A-B #= 320,
A #= 21*B.
当我在 SWI 中调用它时，我得到：
?- problem(A,B).
320+B#=A,
21*B#=A.
而在 GNU 中，我得到的正确答案是：
| ?- problem(A,B).
A = 336
B = 16
这是怎么回事？理想情况下，我希望在 SWI 中获得正确的结果，因为它是一个更强大的环境。
这是一个很好的观察。
乍一看，SWI 无法像 GNU Prolog 那样有效传播，这无疑是一个缺点。
然而，还有其他因素在起作用。
核心问题
首先，请在 GNU Prolog 中尝试以下查询：
| ?- X #= X.
声明地，查询可以理解为：X 是一个 整数 。原因是：
(#=)/2 仅适用于 整数 X #= X 不以任何方式限制整数 X 的域。
然而，至少在我的机器上，GNU Prolog 的回答是：
X = _#0(0..268435455)
所以其实整数X的域已经变成了有限虽然我们没有限制它无论如何！
为了比较，我们在 SICStus Prolog 中得到例如：
?- X #= X.
X in inf..sup.
这表明整数X的域没有受到任何限制。
用 CLP(Z) 复制结果
让我们公平竞争。我们可以通过 人为地 将变量的域限制为 有限 区间 0..2[= 来使用 SWI-Prolog 模拟上述情况100=]64:
?- problem(A, B),
Upper #= 2^64,
[A,B] ins 0..Upper.
作为回应，我们现在用 SWI-Prolog 得到：
A = 336,
B = 16,
Upper = 18446744073709551616.
因此，将域限制为整数的 有限 子集使我们能够使用 SWI-Prolog 的 CLP(FD) 求解器复制我们从 GNU Prolog 知道的结果或其继任者，CLP(Z).
这样做的原因
CLP(Z) 的目标是完全用高级声明替代替换用户程序中的低级算术谓词可以用作真实关系，当然也可以用作 drop-in 替换。出于这个原因，CLP(Z) 支持 无界 整数，它可以增长到计算机内存允许的大小。在 CLP(Z) 中，所有整数变量的默认定义域是 all 个整数的集合。这意味着只要其中一个域是无限的，就不会执行应用于 有界 域的某些传播。
例如：
?- X #> Y, Y #> X.
X#=<Y+ -1,
Y#=<X+ -1.
这是一个条件答案：原始查询是可满足的iff所谓的残差约束 是可满足的。
相比之下，我们得到有限域：
?- X #> Y, Y #> X, [X,Y] ins -5000..2000.
false.
只要所有域都是有限的，我们预计相关系统的传播强度大致相同。
固有的限制
求解整数方程通常是 undecidable。因此，对于 CLP(Z)，我们知道 没有 决策算法总能产生正确的结果。
因此，您有时会得到 剩余约束 而不是无条件答案。在 finite 整数集上，方程当然是可判定的：如果所有域都是有限的并且您没有得到具体的解决方案作为答案，请使用 枚举谓词之一 详尽地寻找解决方案。
在可以对无限整数集进行推理的系统中，您迟早会遇到这种现象，必然。
我在 Prolog 中写了一个快速谓词来试用 CLP(FD) 及其求解方程组的能力。
problem(A, B) :-
A-B #= 320,
A #= 21*B.
当我在 SWI 中调用它时，我得到：
?- problem(A,B).
320+B#=A,
21*B#=A.
而在 GNU 中，我得到的正确答案是：
| ?- problem(A,B).
A = 336
B = 16
这是怎么回事？理想情况下，我希望在 SWI 中获得正确的结果，因为它是一个更强大的环境。
这是一个很好的观察。
乍一看，SWI 无法像 GNU Prolog 那样有效传播，这无疑是一个缺点。
然而，还有其他因素在起作用。
核心问题
首先，请在 GNU Prolog 中尝试以下查询：
| ?- X #= X.
声明地，查询可以理解为：X 是一个 整数 。原因是：
(#=)/2仅适用于 整数X #= X不以任何方式限制整数X的域。
然而，至少在我的机器上，GNU Prolog 的回答是：
X = _#0(0..268435455)
所以其实整数X的域已经变成了有限虽然我们没有限制它无论如何！
为了比较，我们在 SICStus Prolog 中得到例如：
?- X #= X. X in inf..sup.
这表明整数X的域没有受到任何限制。
用 CLP(Z) 复制结果
让我们公平竞争。我们可以通过 人为地 将变量的域限制为 有限 区间 0..2[= 来使用 SWI-Prolog 模拟上述情况100=]64:
?- problem(A, B), Upper #= 2^64, [A,B] ins 0..Upper.
作为回应，我们现在用 SWI-Prolog 得到：
A = 336, B = 16, Upper = 18446744073709551616.
因此，将域限制为整数的 有限 子集使我们能够使用 SWI-Prolog 的 CLP(FD) 求解器复制我们从 GNU Prolog 知道的结果或其继任者，CLP(Z).
这样做的原因
CLP(Z) 的目标是完全用高级声明替代替换用户程序中的低级算术谓词可以用作真实关系，当然也可以用作 drop-in 替换。出于这个原因，CLP(Z) 支持 无界 整数，它可以增长到计算机内存允许的大小。在 CLP(Z) 中，所有整数变量的默认定义域是 all 个整数的集合。这意味着只要其中一个域是无限的，就不会执行应用于 有界 域的某些传播。
例如：
?- X #> Y, Y #> X. X#=<Y+ -1, Y#=<X+ -1.
这是一个条件答案：原始查询是可满足的iff所谓的残差约束 是可满足的。
相比之下，我们得到有限域：
?- X #> Y, Y #> X, [X,Y] ins -5000..2000. false.
只要所有域都是有限的，我们预计相关系统的传播强度大致相同。
固有的限制
求解整数方程通常是 undecidable。因此，对于 CLP(Z)，我们知道 没有 决策算法总能产生正确的结果。
因此，您有时会得到 剩余约束 而不是无条件答案。在 finite 整数集上，方程当然是可判定的：如果所有域都是有限的并且您没有得到具体的解决方案作为答案，请使用 枚举谓词之一 详尽地寻找解决方案。
在可以对无限整数集进行推理的系统中，您迟早会遇到这种现象，必然。