示例通道约束 ECLiPSe
Example channelling constraints ECLiPSe
有人可以提供一个简单的通道约束示例吗？
通道约束用于组合约束问题的观点。 Handbook of Constraint Programming 很好地解释了它的工作原理以及它为什么有用：
The search variables can be the variables of one of the viewpoints, say X1 (this is discussed further below). As
search proceeds, propagating the constraints C1 removes values from the domains of the
variables in X1. The channelling constraints may then allow values to be removed from
the domains of the variables in X2. Propagating these value deletions using the constraints
of the second model, C2, may remove further values from these variables, and again these
removals can be translated back into the first viewpoint by the channelling constraints. The
net result can be that more values are removed within viewpoint V1 than by the constraints
C1 alone, leading to reduced search.
我不明白这是如何实现的。这些约束到底是什么，它们在实际问题中看起来如何？一个简单的例子会很有帮助。
这是一个简单的例子，可以在 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)
再见
当在模型中以不止一种方式表示问题的各个方面时，使用通道约束。然后他们有必要同步这些多重表示，即使他们自己没有对问题的某个方面进行建模。
通常，在对具有约束的问题建模时，您可以通过多种方式选择变量。例如，在调度问题中，您可以选择
- 每个作业的整数变量（指示哪台机器执行该作业）
- 每台机器的整数变量（表示它执行的作业）
- 布尔矩阵（表示哪个作业在哪台机器上运行）
- 或更奇特的东西
在一个足够简单的问题中，您选择最容易制定问题约束的表示。然而，在具有许多异构约束的现实生活问题中，通常不可能找到这样一个单一的最佳表示：一些约束最好用一种类型的变量表示，而另一些则用另一种。
在这种情况下，您可以使用多组变量，并在最方便的变量组上制定每个单独的问题约束。当然，您最终会遇到多个独立的子问题，孤立地解决这些子问题不会为您提供整个问题的解决方案。但是通过添加通道约束，可以同步变量集，从而重新连接子问题。结果是整个问题的有效模型。
正如手册中的引述所暗示的那样，在这样的公式中仅对一个变量集 ("viewpoints") 执行搜索就足够了，因为其他变量的值由通道隐含约束。
两个表示之间的通道的一些常见示例是：
整数变量和布尔数组：
考虑一个整数变量 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 约束。
Start/End整数变量和布尔数组（时间表）：
我们有整数变量 S,E 指示 activity 的开始和结束时间。另一方面，布尔数组 Bs[N] 使得 Bs[T] = 1 当且仅当 activity 发生在时间 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) ).
双重表示Job/Machine整型变量：
这里，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)) that can directly handle set-variables, these can be reflected into an array of booleans indicating membership of elements in the set. The library provides a dedicated constraint membership_booleans/2。
如 二元约束满足问题的双视点启发式算法 (P.A.Geelen):
Channelling constraints of two different models allows for the expression of a relationship between two sets of variables, one of each model.
这意味着一个视点中的作业可以转换为另一个视点中的作业，反之亦然，而且，当搜索启动时，
从一个模型中排除的值也可以从另一个模型中排除。
让我举一个我不久前在写数独解算器时实现的例子。
经典观点
在这里，我们以与人类相同的方式解释问题：使用
1 到 9 之间的整数以及所有行、列和块必须恰好包含每个整数一次的定义。
我们可以很容易地在 ECLiPSe 中使用类似的东西来说明这一点：
% Domain
dim(Sudoku,[N,N]),
Sudoku[1..N,1..N] :: 1..N
% For X = rows, cols, blocks
alldifferent(X)
这足以解决数独难题。
二进制布尔视点
然而，人们可以选择用二进制布尔数组表示整数（@jschimpf 在 中显示）。如果不清楚这是做什么的，请考虑下面的小示例（这是 built-in 功能！）：
? 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)
我们现在清楚地看到了模型之间的 link，只需编写代码来引导我们的决策变量。使用 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)
).
此时，我们有一个通道模型，在搜索过程中，如果一个模型中的值被修剪，它的影响也会发生在另一个模型中。这当然会导致进一步的整体约束传播。
推理
为了解释二进制布尔模型对数独游戏的有用性，我们必须首先区分 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 库，用于全局约束，维护广义弧一致性（也称为超弧一致性或域一致性）。 alldifferent/1 约束提供了比边界一致约束更多的修剪机会，但是 保持全域一致性有其成本，在高度约束模型中使用这个库通常会导致损失运行 表现。
正因为如此，我发现尝试使用边界一致 (ic_global) 的 alldifferent 实现以最大化性能并随后尝试通过引导二进制文件来实现域一致性对数独游戏来说很有趣布尔模型。
实验结果
以下是 'platinumblonde' 数独谜题（在 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 多个其他数独游戏实例证实）：
Channelling the binary boolean viewpoint to the bounds consistent standalone implementation produces a slightly less strong constraint propagation behaviour than that of the domain consistent standalone implementation, but with running times ranging from just as long to notably faster.
编辑：att想澄清一下
想象一下表示数独板上某个单元格的域变量的剩余域为 4..9。使用边界一致性，可以保证对于值 4 和 9 都可以找到满足所有约束的其他域值，从而提供一致性。但是，域中的其他值没有明确保证一致性（这就是 'domain consistency'）。
使用二元布尔模型，我们定义了以下两个求和约束：
- 每个二进制布尔数组的和总是等于 1
- 每个row/col/block中每个数组的第N个元素的和总是等于1
额外的约束强度由第二个约束强制执行，除了约束行、列和块外，还隐含地表示："every cell can only contain every digit once"。当仅使用边界一致 alldifferent/1 约束时，不会主动表达此行为！
结论
很明显，通道对于改进独立约束模型非常有用，但是如果新模型的约束强度弱于当前模型，显然，没有将进行改进。另请注意，拥有更受约束的模型并不一定意味着整体性能更好！添加更多约束实际上会减少解决问题所需的回溯量，但如果必须进行更多约束检查，它也可能会增加程序的 运行 次。
有人可以提供一个简单的通道约束示例吗？
通道约束用于组合约束问题的观点。 Handbook of Constraint Programming 很好地解释了它的工作原理以及它为什么有用：
The search variables can be the variables of one of the viewpoints, say X1 (this is discussed further below). As search proceeds, propagating the constraints C1 removes values from the domains of the variables in X1. The channelling constraints may then allow values to be removed from the domains of the variables in X2. Propagating these value deletions using the constraints of the second model, C2, may remove further values from these variables, and again these removals can be translated back into the first viewpoint by the channelling constraints. The net result can be that more values are removed within viewpoint V1 than by the constraints C1 alone, leading to reduced search.
我不明白这是如何实现的。这些约束到底是什么，它们在实际问题中看起来如何？一个简单的例子会很有帮助。
这是一个简单的例子，可以在 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)
再见
当在模型中以不止一种方式表示问题的各个方面时，使用通道约束。然后他们有必要同步这些多重表示，即使他们自己没有对问题的某个方面进行建模。
通常，在对具有约束的问题建模时，您可以通过多种方式选择变量。例如，在调度问题中，您可以选择
- 每个作业的整数变量（指示哪台机器执行该作业）
- 每台机器的整数变量（表示它执行的作业）
- 布尔矩阵（表示哪个作业在哪台机器上运行）
- 或更奇特的东西
在一个足够简单的问题中，您选择最容易制定问题约束的表示。然而，在具有许多异构约束的现实生活问题中，通常不可能找到这样一个单一的最佳表示：一些约束最好用一种类型的变量表示，而另一些则用另一种。
在这种情况下，您可以使用多组变量，并在最方便的变量组上制定每个单独的问题约束。当然，您最终会遇到多个独立的子问题，孤立地解决这些子问题不会为您提供整个问题的解决方案。但是通过添加通道约束，可以同步变量集，从而重新连接子问题。结果是整个问题的有效模型。
正如手册中的引述所暗示的那样，在这样的公式中仅对一个变量集 ("viewpoints") 执行搜索就足够了，因为其他变量的值由通道隐含约束。
两个表示之间的通道的一些常见示例是：
整数变量和布尔数组：
考虑一个整数变量 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 约束。
Start/End整数变量和布尔数组（时间表）：
我们有整数变量 S,E 指示 activity 的开始和结束时间。另一方面，布尔数组 Bs[N] 使得 Bs[T] = 1 当且仅当 activity 发生在时间 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) ).
双重表示Job/Machine整型变量：
这里，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)) that can directly handle set-variables, these can be reflected into an array of booleans indicating membership of elements in the set. The library provides a dedicated constraint membership_booleans/2。
如 二元约束满足问题的双视点启发式算法 (P.A.Geelen):
Channelling constraints of two different models allows for the expression of a relationship between two sets of variables, one of each model.
这意味着一个视点中的作业可以转换为另一个视点中的作业，反之亦然，而且，当搜索启动时， 从一个模型中排除的值也可以从另一个模型中排除。
让我举一个我不久前在写数独解算器时实现的例子。
经典观点
在这里，我们以与人类相同的方式解释问题：使用 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)
我们现在清楚地看到了模型之间的 link，只需编写代码来引导我们的决策变量。使用 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)
).
此时，我们有一个通道模型，在搜索过程中，如果一个模型中的值被修剪，它的影响也会发生在另一个模型中。这当然会导致进一步的整体约束传播。
推理
为了解释二进制布尔模型对数独游戏的有用性，我们必须首先区分 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 库，用于全局约束，维护广义弧一致性（也称为超弧一致性或域一致性）。 alldifferent/1 约束提供了比边界一致约束更多的修剪机会，但是 保持全域一致性有其成本，在高度约束模型中使用这个库通常会导致损失运行 表现。
正因为如此，我发现尝试使用边界一致 (ic_global) 的 alldifferent 实现以最大化性能并随后尝试通过引导二进制文件来实现域一致性对数独游戏来说很有趣布尔模型。
实验结果
以下是 'platinumblonde' 数独谜题（在 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 多个其他数独游戏实例证实）：
Channelling the binary boolean viewpoint to the bounds consistent standalone implementation produces a slightly less strong constraint propagation behaviour than that of the domain consistent standalone implementation, but with running times ranging from just as long to notably faster.
编辑：att想澄清一下
想象一下表示数独板上某个单元格的域变量的剩余域为 4..9。使用边界一致性，可以保证对于值 4 和 9 都可以找到满足所有约束的其他域值，从而提供一致性。但是，域中的其他值没有明确保证一致性（这就是 'domain consistency'）。
使用二元布尔模型，我们定义了以下两个求和约束：
- 每个二进制布尔数组的和总是等于 1
- 每个row/col/block中每个数组的第N个元素的和总是等于1
额外的约束强度由第二个约束强制执行，除了约束行、列和块外，还隐含地表示："every cell can only contain every digit once"。当仅使用边界一致 alldifferent/1 约束时，不会主动表达此行为！
结论
很明显，通道对于改进独立约束模型非常有用，但是如果新模型的约束强度弱于当前模型，显然，没有将进行改进。另请注意，拥有更受约束的模型并不一定意味着整体性能更好！添加更多约束实际上会减少解决问题所需的回溯量，但如果必须进行更多约束检查，它也可能会增加程序的 运行 次。