prolog - CLP(FD)可变域和传播

在上学期的Prolog class 中，在引入CLP的那段时间我落后了一些。现在，我正在努力追赶，并在教授提供给所有学生的上一次考试中尝试了一下。
特别是有一个问题:

在以下查询之后，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)。
我意识到必须在此处做出可行性方面的让步，并且返回的域有时会受到比其限制更少的限制，但是令我惊讶的是，它在如此简单的示例中失败了。
我的问题

我认为这与CLP选择在内部传播(或不传播)各种约束的方式有关，但我不知道它是如何做到的-对我而言，这全都是黑匣子。 CLP如何(确切地说是失败)传播其约束？

是否可以通过重新排序使CLP(FD)适当地应用约束？我已经尝试过在最后添加一个额外的Y #> X，但这并没有改变任何变量域。

最佳答案

在我看来，答案应该是

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.为true，则有解决方案。嘿，这不是真的。

因此，这个答案有点像许多保险合同中的法律条款，他们说，是的，我们将支付，但要保留所有很小的，不可读的印刷品，但实际上，您可以用大的 false 代替那堵微文本墙。

通常，由于在上述系统中定义的CLP(FD)/ CLP(Z)允许提出不确定的问题，因此这种不一致是不可避免的。因此，无论您的约束求解器如何发展，我们都能保证始终存在无法解决的情况。这是科学的数学定律，比重力或速度限制等经验定律要可靠得多。

这里的不一致实际上是工程上的折衷。只要没有人抱怨并且没有令人信服的用例，此类系统的开发人员就不会发现需要改进的理由。毕竟，这样的改进可能会减慢现有的用例。

CLP如何(确切地说是失败)传播其约束？

实际上，对于任何实际大小的问题，没人知道。但这也不是必须的。对于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仅维护每对变量之间的一致性。但是无论如何:这些事情在发展，这是一个考试问题，这令人感到有些惊讶。

有什么方法可以使CLP(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的域是什么？

这是一个模棱两可的问题。给出两个答案。

关于prolog - CLP(FD)可变域和传播，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/59670137/