CLP(FD)可变域及传播

Question

在上学期的Prolog课程中，我在中电推出的时候有点落后。现在我正在努力赶上，在教授提供给所有学生的过去的一次考试中，我已经试过了。

具体而言，有这样一个问题：

在进行以下查询后，在CLP(FD)中决策变量Z的域是什么：

?- X in 1..7, Y in -3..100, Y #> X, Z #\= 0, Z #= Y - X.

在我看来答案应该是

Z in 1..99

但是当我在我的SWI-Prolog安装中运行它时，我得到了

Z in -5.. -1\/1..99

这似乎是基于对X和Y的最大值和最小值的天真比较，而不考虑连接它们的约束(Y #> X)。

我意识到必须在这里做出可行性让步，而返回的域名有时会比它们可能的限制更少，但我惊讶地看到它在这样一个简单的例子上失败了。

我的问题

1. --我假设这与CLP选择如何在内部传播(或不传播)各种约束有关，但我不明白它是如何做到的--对我来说，这都是一个黑匣子。CLP到底是如何传播它的constraints?
2. Is的(或者说是失败的)--有什么方法可以使CLP(FD)适当地应用约束，也许是通过重新排序？我已经尝试过在最后添加一个额外的Y #> X，但是这并没有改变任何变量域。

Answer 1

在我看来答案应该是

Z in 1.99

你怎么能这么肯定你是对的？这是约束的优点之一:您可以最容易地验证这一点：

?- X in 1..7, Y in -3..100, Y #> X, Z #\= 0, Z #= Y -X.
X in 1..7,
Z+X#=Y,
X#=<Y+ -1,
Z in -5.. -1\/1..99,
Y in 2..100.

?- X in 1..7, Y in -3..100, Y #> X, Z #\= 0, Z #= Y -X, Z #< 0.
false.

好吧，现在我相信你说的话。

因此，您在这里发现了一个不一致性，它也存在于SICStus的本机library(clpfd)和library(clpz)中。首先，请注意，给出的答案不是不正确的！它说:是的，只要 X in 1..7, Z+X#=Y, X#=<Y+ -1, Z in -5.. -1\/1..99, Y in 2..100.是真的，就有解决方案。哈拉斯，这不是真的。

因此，这个答案有点像许多保险合同中的法律术语，他们说，“是的，我们会支付的，前提是所有那些小而不可读的打印件，但实际上，你可以用一个巨大的false.来代替那堵微文字墙。”

一般来说，这种不一致是不可避免的，因为中电(FD)/CLP(Z)，如上述系统所定义的，允许提出不可判定的问题。因此，无论您的约束解决程序是如何发展，我们都保证总会有我们无法解决的情况。这是一条科学的、数学的定律，比重力或速度限制等经验性定律更可靠。

这里的矛盾实际上是一种工程上的权衡。只要没有人抱怨，也没有令人信服的用例，这些系统的开发人员就看不到改进的理由。毕竟，这样的改进可能会减缓现有用例的速度。

中国电力公司( constraints?

1. )究竟是如何传播它的
2. 的(或者说失败了)？

事实上，对于任何现实规模的问题，没人知道。但这也没有必要。对于CLP(FD)，基本元素是附加到逻辑变量的域。您可以将它们视为(in)/2目标，如Z in -5.. -1\/1..99。它们之间的联系是实际的约束。在你的例子中，Y #> X和Z #= Y-X。这些约束现在只看到变量的域，并试图保持它们之间的一致性。作为一个更粗的近似，域被看作是区间，因此Z in -5 .. 99而不是上面。(他们中的大多数)看不到的是其他的约束。在这种情况下，Y #> X和Z #= Y-X之间没有直接联系。因此不一致。这种有限的一致性检查更容易实现，而且速度也相当快，而且往往优于更完整的算法。随着更好的算法的发现，事情发生了变化。一个很好的例子是all_distinct/1，它使用Regin的算法维护所有变量之间的一致性，而all_different/1只维护每个变量之间的一致性。但无论如何，这些事情都在演变，这是一个考试问题，这有点令人惊讶。

1. 有没有办法让中电(FD)适当地应用约束.？

?- X in 1..7, Y in -3..100, Y #> X, Z #\= 0, Z #= Y -X, clpfd:contracting([X,Y,Z]).
X in 1..7,
Z+X#=Y,
X#=<Y+ -1,
Z in 1..99,
Y in 2..100.

但是大多数人会忽略这个问题，只需添加labeling([],[X,Y])

Z的领域是什么？

这是一个含糊不清的问题。两者兼而有之。