我不理解Prolog中的label是什么意思。

Question

我不理解Prolog中的label是什么意思。

prologsudokuclpfd

8

我已经仔细阅读了手册和文档，但仍然不理解。我正在尝试实现数独（Sudoku）解决方案，在写出游戏的所有其他规则后，根据我的老师的指示添加了标签（Board）。

然而，我仍然不知道它是如何工作的或者它在做什么。难道其他约束条件（我有检查数字必须是1到9之间、行必须都不同等）本身不能给出答案吗？

- NewGuy

1

你需要理解答案和解决方案之间的区别。参考：此, 那。通过标记，我们可以将答案简化为具体的解决方案。 - false

2个回答

1

粗略地说，约束编程分为两个阶段：约束传播和搜索。

仅使用约束传播可以给出具体值，并且通常会这样做。但一般来说，它只会将域（变量的可能值集合）缩小到一个更小的子集，然后需要搜索（从通过约束传播获得的子集中标记值）。

非常简单的示例（伪代码）：

A #:: 0..1,
B #:: 0..1,
A #\= B

约束传播本身不能解决这个问题，它甚至无法减少A或B的领域 - 它只能创建一个延迟约束。然后，在搜索（标签）尝试为A赋值0之后，延迟的约束触发，并将B的领域减少到{1}。

相比之下，这可以仅通过约束传播来解决：

A #:: 1,
B #:: 0..1,
A #\= B

- Sergii Dymchenko

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- false · Accepted Answer

如果你想快速学习Prolog和CLP(FD)，可以使用Prolog的顶层shell进行实验，直到你感觉舒适为止。实际上，关于CLP(FD)和Prolog的一切都可以在那里解释;或者几乎可以。不需要编写文件，所有东西都能放在一行中。是的，我知道，我们的父母警告我们：孩子啊，答应我，永远不要只写一行代码。但你会学得更快。

所以，你有?-在等待吗？

在传统的Prolog（没有约束）中，从一个查询中得到的是所谓的“回答替代”。在许多情况下，这个回答替代已经描述了解决方案。如果每个变量都找到了一个自由变量项，那么就是这种情况。让我们看一个具体的例子，描述一个包含五个元素的列表，其中每个元素都是1到5之间的值。在这种情况下，对于不同的L值可以找到解决方案。

?- N = 5, length(L,N),maplist(between(1,N),L).
   N = 5, L = [1,1,1,1,1]
;  N = 5, L = [1,1,1,1,2]
;  N = 5, L = [1,1,1,1,3]
;  ... .

Prolog只会显示一个解决方案（暗示您将对其感到满意，它有点懒，不严格）。要获得全部解决方案，请输入SPACE或;。试着尝试一下，看看有多少个解决方案...

总共有5^5个解决方案。如果您只想从中选择一些解决方案，则这并不是很实用。使用这种方式来表示大量解决方案的集合效果相当低效。然后，考虑一下无限集合！Prolog或任何有限存在如何枚举无限集合？由于我们是有限的，因此只能开始这样做。

为了克服这个问题，Prolog并不总是被迫显示具体值即解决方案，而是可以通过展示答案来略微掩盖它们：

?- N = 5, length(L,N).
   N = 5, L = [_A,_B,_C,_D,_E].

这个答案(-substitution)包含了所有5^5个以上的答案，以及很多很多更多的，比如L = [stack,over,flow,dot,com]。实际上，它描述了一个无限解集！难道我没有说过我们有限的存在做不到吗？只要我们满足于得到答案而不是具体的解，就可以突破不可能。

这个想法可以扩展到描述更具体的解集。所有的解都可以用单一的答案来表示。对于整数解集，我们可以使用library(clpfd)。像这样使用：

?- use_module(library(clpfd)).

?- asserta(clpfd:full_answer).  % only necessary for SICStus

现在我们可以重新陈述我们最初的查询（在SWI中，您可以按光标上 ↑键来获取它）：

?- N = 5, length(L,N),L ins 1..N.
   N = 5, L = [_A,_B,_C,_D,_E],
   _A in 1..5, _B in 1..5, _C in 1..5, _D in 1..5,_E in 1..5.

现在所有3125种解决方案都可以用一个答案来简洁地描述。(3125？那是5^5)。我们可以继续陈述进一步的要求，比如它们都不同：

?- N = 5, length(L,N),L ins 1..N, all_different(L).
   N = 5, L = [_A,_B,_C,_D,_E],
   _A in 1..5,_B in 1..5,_C in 1..5,_D in 1..5,_E in 1..5,
   all_different([_A,_B,_C,_D,_E]).

（实际上）所有约束条件的共同点是它们不会枚举解决方案，而是尝试维护一致性。让我们试试这个例子，假设第一个元素应该为1：

?- N = 5, length(L,N),L ins 1..N, all_different(L), L = [1|_].
   N = 5, L = [1,_A,_B,_C,_D],
   _A in 2..5,_B in 2..5,_C in 2..5,_D in 2..5,
   all_different([1,_A,_B,_C,_D]).

你看到效果了吗？他们迅速更改了域名！现在它们全部在2..5内。

而它们应该全部在1..4内：

?- N = 5, length(L,N),L ins 1..N, all_different(L), L = [1|_], L ins 1..4.
   N = 5, L = [1,_A,_B,_C,_D],
   _A in 2..4,_B in 2..4,_C in 2..4,_D in 2..4,
   all_different([1,_A,_B,_C,_D]).

再次更新了它们。但是...想想吧：还剩下4个变量，它们应该都不同，但它们只有3个不同的值。

所以我们发现Prolog有点懒惰了。实际上有一个更好的约束叫做all_distinct/1，现在会失败，但是无论系统有多少聪明的约束条件，总会存在这样的不一致性。问问哥德尔教授。唯一的解决方法是出错或无限循环。

因此，我们需要另一种方法来确保答案描述真实解。进入标记！使用label/1或labeling/2，我们可以消除所有奇怪的约束并处理不一致性：

?- N = 5, length(L,N),L ins 1..N, all_different(L), L = [1|_], L ins 1..4, labeling([], L).
   false.
?- N = 5, length(L,N),L ins 1..N, all_different(L), L = [1|_], labeling([], L).
   N = 5, L = [1,2,3,4,5]
;  N = 5, L = [1,2,3,5,4]
;  N = 5, L = [1,2,4,3,5]
;  ... .

我们怎样才能确定这些是真正的解决方案呢？很简单：它们除了答案替换之外不包含任何额外的目标¹。因为如果我们忘记了一些:

?- N = 5, length(L,N),L ins 1..N, all_different(L), L = [1,B,C|_], labeling([],[B,C]).
   N = 5, L = [1,2,3,_A,_B], B = 2, C = 3,
   _A in 4..5, _B in 4..5,
   all_different([1,2,3,_A,_B]),

他们会显示。

SWI的labeling/2有一个非常有用的保证：

标记始终是完整的、始终终止，并且不产生多余的解决方案。

1由于SWI顶级不显示所有约束条件，您需要在其周围包装call_residue_vars(Goal, Vs)。但对于简单的顶级查询，上面的内容已经足够了。