CLP(FD) 可变域和传播
CLP(FD) variable domains & propagation
在上个学期的 Prolog 课程中，我在引入 CLP 时落后了一点。现在我正在努力赶上，并尝试参加教授提供给所有学生的过去考试。
特别是有这个问题：
What is the domain of the decision variable Z in CLP(FD) after the following query:
?- 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，但这并没有改变任何变量域。
It seems to me that the answer should be
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.是真的。 Helas，这不是真的。
所以这个答案有点像许多保险合同中的法律术语，他们说，是的，我们会支付，前提是所有那些微小的、不可读的印刷品保留下来，但实际上你可以用一个大胖子代替那堵缩微文本墙false.
一般来说，这种不一致是不可避免的，因为在上述系统中定义的 CLP(FD)/CLP(Z) 允许制定 不可判定的 问题。因此，无论您的约束求解器如何发展，我们都可以保证总会有我们无法解决的情况。这是一个科学的数学定律，比重力或速度限制等经验定律更可靠。
这里的不一致实际上是一种工程权衡。只要没有人抱怨并且没有令人信服的用例，此类系统的开发人员就不会看到改进的理由。毕竟，这样的改进可能会降低现有用例的速度。
- How, exactly (or failing that, approximately), does CLP propagate its constraints?
实际上，对于任何实际大小的问题，没有人知道。但这也不是必须的。在 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 只保持每对变量之间的一致性。但无论如何：这些东西在演变，这是一道考试题，有点令人惊讶。
- Is there any way to make CLP(FD) apply the constraint appropriately ...?
?- 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])
- What is the domain of
Z?
这是一个模棱两可的问题。将两者都作为答案。
在上个学期的 Prolog 课程中，我在引入 CLP 时落后了一点。现在我正在努力赶上，并尝试参加教授提供给所有学生的过去考试。
特别是有这个问题：
What is the domain of the decision variable Z in CLP(FD) after the following query:
?- 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，但这并没有改变任何变量域。
It seems to me that the answer should be
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.是真的。 Helas，这不是真的。
所以这个答案有点像许多保险合同中的法律术语，他们说，是的，我们会支付，前提是所有那些微小的、不可读的印刷品保留下来，但实际上你可以用一个大胖子代替那堵缩微文本墙false.
一般来说，这种不一致是不可避免的，因为在上述系统中定义的 CLP(FD)/CLP(Z) 允许制定 不可判定的 问题。因此，无论您的约束求解器如何发展，我们都可以保证总会有我们无法解决的情况。这是一个科学的数学定律，比重力或速度限制等经验定律更可靠。
这里的不一致实际上是一种工程权衡。只要没有人抱怨并且没有令人信服的用例，此类系统的开发人员就不会看到改进的理由。毕竟，这样的改进可能会降低现有用例的速度。
- How, exactly (or failing that, approximately), does CLP propagate its constraints?
实际上，对于任何实际大小的问题，没有人知道。但这也不是必须的。在 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 只保持每对变量之间的一致性。但无论如何：这些东西在演变，这是一道考试题，有点令人惊讶。
- Is there any way to make CLP(FD) apply the constraint appropriately ...?
?- 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])
- What is the domain of
Z?
这是一个模棱两可的问题。将两者都作为答案。