prolog - 示例通道约束 ECLiPSe

Question

有人可以提供一个简单的通道约束示例吗？

通道约束用于组合约束问题的观点。约束编程手册很好地解释了它的工作原理以及它为什么有用：

搜索变量可以是其中一个视点的变量，比如 X1（这将在下面进一步讨论）。随着搜索的进行，传播约束 C1 会从 X1 中变量的域中删除值。然后，通道约束可以允许从 X2 中变量的域中删除值。使用第二个模型 C2 的约束传播这些值删除可能会从这些变量中删除更多值，并且这些删除可以再次通过通道约束转换回第一个视点。最终结果可能是，在视点 V1 中删除的值比仅通过约束 C1 删除的值更多，从而导致搜索减少。

我不明白这是如何实现的。这些约束到底是什么，它们在实际问题中看起来如何？一个简单的例子会很有帮助。

score 5 · Accepted Answer

当在模型中以不止一种方式表示问题的各个方面时，将使用通道约束。然后它们需要同步这些多个表示，即使它们本身并没有对问题的某个方面进行建模。

通常，在对具有约束的问题进行建模时，您有多种选择变量的方法。例如，在调度问题中，您可以选择

每个作业的整数变量（指示哪台机器执行该作业）
每台机器的整数变量（指示它执行的工作）
布尔矩阵（指示哪个作业在哪台机器上运行）
或更异国情调的东西

在一个足够简单的问题中，您选择最容易制定问题约束的表示。然而，在具有许多异构约束的现实生活问题中，通常不可能找到这样一个最佳表示：一些约束最好用一种类型的变量来表示，而另一些则用另一种。

在这种情况下，您可以使用多组变量，并在最方便的变量集上制定每个单独的问题约束。当然，您最终会遇到多个独立的子问题，孤立地解决这些问题不会为您提供整个问题的解决方案。但是通过添加通道约束，变量集可以同步，子问题因此可以重新连接。结果是整个问题的有效模型。

正如手册中的引文所暗示的那样，在这样的公式中，仅对变量集（“视点”）之一执行搜索就足够了，因为其他变量的值隐含在通道约束中。

在两个表示之间进行通道的一些常见示例是：

整数变量和布尔数组：考虑一个整数变量T，指示事件发生的时间段1..N，以及一个布尔数组，Bs[N]以便Bs[T] = 1当一个事件发生在时间段T中。在 ECLiPSe 中：

    T #:: 1..N,
    dim(Bs, [N]), Bs #:: 0..1,

然后可以设置两个表示之间的通道

    ( for(I,1,N), param(T,Bs) do Bs[I] #= (T#=I) )

T这将在和之间双向传播信息Bs。实现这种通道的另一种方法是特殊用途的bool_channeling/3约束。

开始/结束整数变量和布尔数组（时间表）：我们有整数变量S,E指示活动的开始和结束时间。另一方面，一个布尔数组Bs[N]，Bs[T] = 1如果活动发生在 time T。在 ECLiPSe 中：

    [S,E] #:: 1..N,
    dim(Bs, [N]), Bs #:: 0..1,

通道可以通过以下方式实现

    ( for(I,1,N), param(S,E,Bs) do Bs[I] #= (S#=<I and I#=<E) ).

对偶表示作业/机器整数变量：这里Js[J] = M表示作业J在机器上执行M，而对偶公式Ms[M] = J表示机器M执行作业J

    dim(Js, [NJobs]), Js #:: 0..NMach,
    dim(Ms, [NMach]), Ms #:: 1..NJobs,

通道是通过

    ( multifor([J,M],1,[NJobs,NMach]), param(Js,Ms) do
        (Js[J] #= M) #= (Ms[M] #= J)
    ).

设置变量和布尔数组：如果您使用可以直接处理集合变量的求解器（例如library(ic_sets)），这些可以反映到布尔数组中，指示集合中元素的成员资格。该库为此目的提供了一个专用的约束membership_booleans/2 。

score 5 · Accepted Answer

如二元约束满足问题的双视点启发式 (PA Geelen)所述：

两个不同模型的通道约束允许表达两组变量之间的关系，每个模型一个。

这意味着一个观点的分配可以转换为另一个观点的分配，反之亦然，并且当搜索开始时，一个模型中的排除值也可以从另一个模型中排除。

让我举一个我不久前在编写数独求解器时实现的示例。

经典观点

在这里，我们以与人类相同的方式来解释这个问题：使用 1 到 9 之间的整数以及所有行、列和块必须包含每个整数一次的定义。

我们可以很容易地在 ECLiPSe 中使用类似这样的方式声明这一点：

% Domain
dim(Sudoku,[N,N]),
Sudoku[1..N,1..N] :: 1..N

% For X = rows, cols, blocks
alldifferent(X)

这还足以解决数独难题。

二进制布尔视点

但是，可以选择用二进制布尔数组表示整数（在@jschimpf的答案中显示）。如果不清楚这是做什么的，请考虑下面的小示例（这是内置功能！）：

? ic_global:bool_channeling(Digit, [0,0,0,1,0], 1).
    Digit = 4
    Yes (0.00s cpu)
? ic_global:bool_channeling(Digit, [A,B,C,D], 1), C = 1.
    Digit = 3
    A = 0
    B = 0
    C = 1
    D = 0
    Yes (0.00s cpu)

如果我们用这个模型来表示一个数独，每个数字都将被它的二进制布尔数组替换，并且可以编写相应的约束。对于这个答案来说微不足道，我不会包含约束的所有代码，但是单个总和约束足以解决其二进制布尔表示形式的数独难题。

引导

现在，将这两个视点与相应的约束模型结合起来，就可以在它们之间进行交流，看看是否有任何改进。

由于这两种模型仍然只是 NxN 板，因此不存在表示维度的差异，并且通道变得非常容易。

让我首先给你最后一个例子，说明在我们的两个模型中填充整数 1..9 的块的样子：

% Classic viewpoint
1 2 3
4 5 6
7 8 9

% Binary Boolean Viewpoint
[](1,0,0,0,0,0,0,0,0)  [](0,1,0,0,0,0,0,0,0)  [](0,0,1,0,0,0,0,0,0) 
[](0,0,0,1,0,0,0,0,0)  [](0,0,0,0,1,0,0,0,0)  [](0,0,0,0,0,1,0,0,0) 
[](0,0,0,0,0,0,1,0,0)  [](0,0,0,0,0,0,0,1,0)  [](0,0,0,0,0,0,0,0,1)

我们现在清楚地看到了模型之间的联系，只需编写代码来引导我们的决策变量。使用Sudoku和BinBools作为我们的板，代码看起来像：

( multifor([Row,Col],1,N), param(Sudoku,BinBools,N) 
do
  Value is Sudoku[Row,Col], 
  ValueBools is BinBools[Row,Col,1..N], 
  ic_global:bool_channeling(Value,ValueBools,1) 
).

在这一点上，我们有一个通道模型，在搜索过程中，如果值在一个模型中被修剪，它的影响也会出现在另一个模型中。这当然可以导致进一步的整体约束传播。

推理

为了解释二元布尔模型对数独谜题的有用性，我们必须首先区分alldifferent/1ECLiPSe 提供的一些实现：

这在实践中意味着什么可以显示如下：

? [A, B, C] :: [0..1], ic:alldifferent([A, B, C]). 
  A = A{[0, 1]} 
  B = B{[0, 1]} 
  C = C{[0, 1]} 
  There are 3 delayed goals. 
  Yes (0.00s cpu) 

? [A, B, C] :: [0..1], ic_global:alldifferent([A, B, C]). 
  No (0.00s cpu)

由于尚未使用前向检查（ic 库）进行任何分配，因此尚未检测到查询的无效性，而 Bounds Consistent 版本会立即注意到这一点。在通过高度约束的模型进行搜索和回溯时，这种行为可能会导致约束传播的显着差异。

在这两个库之上还有一个 ic_global_gac 库，用于维护广义弧一致性（也称为超弧一致性或域一致性）的全局约束。这种 alldifferent/1 约束提供了比边界一致约束更多的剪枝机会，但保持全域一致性是有代价的，在高度约束的模型中使用这个库通常会导致运行性能下降。

正因为如此，我发现数独谜题很有趣，尝试使用 alldifferent 的边界一致 (ic_global) 实现来最大化性能，然后尝试通过引导二进制布尔模型自己接近域一致性。

实验结果

下面是 'platinumblonde' Sudoku 谜题的回溯结果（在The Chaos Within Sudoku、M. ErcseyRavasz 和 Z. Toroczkai 中被称为最难、最混乱的数独谜题）分别使用前向检查、边界一致性、域一致性、独立的二进制布尔模型，最后是通道模型：

      (ic)   (ic_global)  (ic_global_gac)  (bin_bools)  (channelled)
BT    6 582      43             29             143           30

正如我们所看到的，我们的通道模型（使用边界一致性（ic_global））仍然需要比域一致性实现多一个回溯，但它的性能肯定比独立边界一致性版本更好。

当我们现在看一下运行时间（结果是计算多次执行的平均值的结果，这是为了避免极端情况），不包括前向检查实现，因为它已被证明对于解决数独难题不再有趣：

          (ic_global)  (ic_global_gac)  (bin_bools)  (channelled)
Time(ms)     180ms          510ms           100ms        220ms

看看这些结果，我认为我们可以成功地结束实验（这些结果得到了 20 多个其他数独谜题实例的证实）：

将二进制布尔视点引导到边界一致的独立实现会产生比域一致的独立实现稍弱的约束传播行为，但运行时间从一样长到明显更快。

编辑：试图澄清

想象一下代表数独板上单元格的某个域变量的剩余域为 4..9。使用边界一致性，可以保证对于值 4 和 9 都可以找到满足所有约束的其他域值，从而提供一致性。但是，对于域中的其他值，没有明确保证一致性（这就是“域一致性”）。

使用二进制布尔模型，我们定义了以下两个和约束：

每个二进制布尔数组的总和始终等于 1
每个行/列/块中每个数组的每个第 N 个元素的总和始终等于 1

额外的约束强度由第二个约束强制执行，除了约束行、列和块外，它还隐含地说：“每个单元格只能包含每个数字一次”。仅使用边界一致 alldifferent/1 约束时，不会主动表达此行为！

结论

很明显，通道对于改进独立的约束模型非常有用，但是如果新模型的约束强度弱于当前模型，显然不会进行任何改进。另请注意，拥有更受约束的模型并不一定也意味着整体性能更好！添加更多约束实际上会减少解决问题所需的回溯量，但如果必须进行更多约束检查，它也可能会增加程序的运行时间。

score 1 · Accepted Answer

这是一个简单的例子，在 SWI-Prolog 中工作，但也应该在 ECLiPSe Prolog 中工作（在后面你必须使用 (::)/2 而不是 (in)/2）：

约束 C1：

 ?- Y in 0..100.
 Y in 0..100.

约束 C2：

 ?- X in 0..100.
 X in 0..100.

通道约束：

 ?- 2*X #= 3*Y+5.
 2*X#=3*Y+5.

全部一起：

?- Y in 0..100, X in 0..100, 2*X #= 3*Y+5.
Y in 1..65,
2*X#=3*Y+5,
X in 4..100.

所以通道约束在两个方向上都起作用，它减少了 C1 的域以及 C2 的域。

一些系统使用迭代方法，导致这种通道可能需要相当长的时间，这是一个示例，在 SWI-Prolog 中需要大约 1 分钟来计算：

?- time(([U,V] ins 0..1_000_000_000, 36_641*U-24 #= 394_479_375*V)).
% 9,883,559 inferences, 53.616 CPU in 53.721 seconds 
(100% CPU, 184341 Lips)
U in 346688814..741168189,
36641*U#=394479375*V+24,
V in 32202..68843.

另一方面，ECLiPSe Prolog 眨眼间就完成了：

[eclipse]: U::0..1000000000, V::0..1000000000, 
              36641*U-24 #= 394479375*V.
U = U{346688814 .. 741168189}
V = V{32202 .. 68843}
Delayed goals:
     -394479375 * V{32202 .. 68843} + 
     36641 * U{346688814 .. 741168189} #= 24
Yes (0.11s cpu)

再见

prolog - 示例通道约束 ECLiPSe

3 回答 3

Related

Reference