作为学习练习，我正在尝试使用 Prolog 解决逻辑难题，并且我认为我已经使用 GNU Prolog 有限域求解器正确地映射了问题。
当我运行求解函数时，Prolog 会返回：是的，并且变量列表都在 0..1 范围内（布尔值，因为我已经限制了它们）。问题是，当我尝试添加 fd_labeling(Solution) 子句时，Prolog 关于面孔并吐出：不。
我是这种语言的新手，我似乎找不到任何攻击路线来弄清楚为什么一切似乎都有效，直到我真正要求它标记答案......
2 回答
4
显然，您没有“正确”地将问题映射到 FD，因为当您尝试标记变量时会得到“否”。
你在约束逻辑编程中所做的是建立一个约束模型，其中你有一个带有域的变量（在你的例子中是带有域 [0,1] 的布尔值），以及这些变量之间的许多约束。每个约束都有一个传播规则，该规则试图实现发布约束的变量域的一致性。不一致的值将从域中删除。一致性有多种类型，但它们有一个共同点：约束本身通常不会为您提供完整的解决方案，甚至不会告诉您是否存在约束模型的解决方案。
例如，假设您有两个变量 X 和 Y，都具有域 [1..10] 和约束 X < Y。然后传播规则将从 Y 的域中删除值 1 并从域中删除 10的 X。然后它将停止，因为域现在是一致的：对于一个域中的每个值，另一个域中存在一个值，因此满足约束。
为了获得解决方案（所有变量都绑定到值），您需要标记变量。每个标签都会唤醒附加到标签变量的约束，触发另一轮传播。这将导致解决方案（所有变量绑定到值，答案：是）或失败（在搜索树的每个分支中，某些变量以空域结束，答案：否）
由于每个约束只针对发布它的变量域的一致性，因此在传播阶段可能不会检测到由约束组合引起的不可行性。例如，具有域 [1..2] 和成对不等式约束的三个变量 X、Y、Z。这似乎发生在您的约束模型中。
如果您确定必须有解决难题的方法，那么您的约束模型包含一些不可行性。也许对约束条件的敏锐观察已经足以发现它。
如果您没有看到任何明显的不可行性（例如，一些矛盾的约束，如上面的不等式示例），您需要调试您的程序。如果可能，不要使用内置的标签谓词，而是自己编写。然后，您可以添加一些输出谓词，使您可以跟踪实例化了哪些变量，以及这导致了布尔决策变量的哪些变化，或者它是否导致了失败。
于 2011-11-07T08:10:03.997 回答
2
（@twinterer 已经给出了解释，我的回答试图从不同的角度来看）
当您向 Prolog 输入查询时，您得到的是一个答案。通常一个答案包含一个解决方案，有时它包含几个解决方案，有时它根本不包含任何解决方案。这两个概念经常被混淆。让我们看一下 GNU Prolog 的示例：
| ?- length(Vs,3), fd_domain_bool(Vs).
Vs = [_#0(0..1),_#19(0..1),_#38(0..1)]
yes
在这里，我们有一个包含 8 个解决方案的答案。那是：
| ?- length(Vs,3), fd_domain_bool(Vs), fd_labeling(Vs).
Vs = [0,0,0] ? ;
Vs = [0,0,1] ? ;
...
Vs = [1,1,1]
yes
现在是另一个查询。这就是@twinterer 提到的例子。
| ?- length(Vs,3), fd_domain_bool(Vs), fd_all_different(Vs).
Vs = [_#0(0..1),_#19(0..1),_#38(0..1)]
yes
答案看起来和以前一样。但是，它不再包含解决方案。
| ?- length(Vs,3), fd_domain_bool(Vs), fd_all_different(Vs), fd_labeling(Vs).
no
理想情况下，在这种情况下，顶层不会说“是”而是“也许”。事实上，最早的约束系统之一 CLP(R) 就是这样做的。
另一种使这变得不那么神秘的方法是显示所涉及的实际约束。SWI 这样做：
?- length(Vs,3), Vs ins 0..1, all_different(Vs).
Vs = [_G565,_G568,_G571],
_G565 in 0..1,
all_different([_G565,_G568,_G571]),
_G568 in 0..1,
_G571 in 0..1.
?- length(Vs,3), Vs ins 0..1, all_different(Vs), labeling([], Vs).
false.
因此，SWI 向您展示了获得具体解决方案必须满足的所有约束条件。将 SWI 的答案解读为：是的，有一个解决方案，前提是所有这些精美的印刷品都是真的！ 唉，细则是假的。
解决此问题的另一种方法是获得all_different/1具有更强一致性的实现。但这仅适用于特定情况。
?- length(Vs,3), Vs ins 0..1, all_distinct(Vs).
false.
在一般情况下，您不能期望系统保持全局一致性。原因：
保持一致性可能非常昂贵。将此类决定委托给标签通常会更好。事实上，简单
all_different/1往往比all_distinct/1.更好的一致性算法通常非常复杂。
在一般情况下，保持全局一致性是一个无法确定的问题。
于 2011-11-07T23:25:33.297 回答