prolog - channel 约束示例ECLiPSe

Question

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

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


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


我不知道这是如何实现的。这些约束到底是什么，它们在实际问题中的外观如何？一个简单的例子将非常有帮助。

Answer 1

如二元约束满足问题的双重观点启发法（P.A. Geelen）中所述：


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


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

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

经典观点

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

我们可以使用类似以下内容的内容在ECLiPSe中轻松声明：

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

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

这就足以解决数独难题。

二进制布尔观点

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

?­ 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)

如果使用此模型表示Sudoku，则每个数字都将替换为其二进制布尔数组，并且可以编写相应的约束。对于这个答案而言，这是微不足道的，我将不包括约束的所有代码，但是单个和约束仍然足以解决其二进制布尔表示形式中的Sudoku难题。

引导

现在，将这两种观点与相应的受约束模型一起使用，就有机会在它们之间进行引导，并查看是否进行了任何改进。

由于两个模型仍然只是一个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) 
).

至此，我们有了一个通道模型，在搜索过程中，如果其中一个模型中的值被修剪，则其影响也将在另一个模型中发生。这样当然可以导致进一步的整体约束传播。

推理

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



在实践中，这意味着什么：

?­ [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库）进行任何分配，因此尚未检测到查询的无效性，而“边界一致”版本会立即注意到这一点。在通过高度约束的模型进行搜索和回溯时，此行为会导致约束传播方面的显着差异。

在这两个库的顶部，有ic_global_gac库，用于针对全局约束，并为其维护了通用弧一致性（也称为超弧一致性或域一致性）。这种全1约束比一致的边界约束提供了更多的修剪机会，但是保留完整的域一致性有其代价，并且在高度约束的模型中使用此库通常会导致运行性能下降。

因此，Sudoku拼图尝试使用alldifferent的边界一致（ic_global）实现以最大程度地提高性能，然后尝试通过引入二进制布尔模型来尝试实现域一致性，这对我来说很有趣。

实验结果

以下是分别使用正向检查，边界一致性，域一致性，独立的“白金”数独谜题（被称为 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））比域一致性实现还需要一个回溯，但是它的性能肯定比独立的边界一致性版本更好。

现在我们来看一下运行时间（结果是在多次执行中计算平均值的结果，这是避免极端情况的结果），排除了正向检查实现，因为事实证明它不再是解决Sudoku难题的有趣方法：

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

查看这些结果，我认为我们可以成功完成实验（这些结果已被20多个Sudoku拼图实例所证实）：


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


编辑：尝试澄清

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

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


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


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

结论

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