Page 150 - 《软件学报》2021年第9期

2774 Journal of Software 软件学报 Vol.32, No.9, September 2021

算法 5. filterDomains(c):set of variables.
begin
1 V:=∅
2 for each x∈scp(c) do
3 for each a of which bitdom(x)[a]=1b do
4 if a doesn’t have a support then
5 bitdom(x)[a]:=0b
6 if bitdom(x) has been filtered then
7 if bitdom(x)=0 then
8 inconsistent:=true
9 return ∅
10 V:=V∪{x}
11 return V
end
算法 3 中,串行过滤算法首先更新表,即移除无效的元组(算法 4 第 4 行);进而过滤论域,即删除在该约束上
不存在支持的值(算法 5 第 5 行);最后返回由被删值的变量所组成的集合.如果有一个变量 x 的论域被删空,即
bitdom(x)的每个位均变为 0b,不相容标识 inconsistent 将被置为 true(算法 5 第 8 行).

2.3 性质分析
因为不同的串行过滤算法有不同的最坏时间复杂度,所以它们的最坏时间复杂度被统一设为 O(T).另外,我
们用 r max 和 d max 分别表示最大的约束元数和最大的初始论域大小,即 r max =max c∈C |scp(c)|,d max =max x∈X |D(x)|.
性质 4. 维持表约束网络 GAC 的串行传播模式的最坏时间复杂度为 O(er max d max T) [17] .
证明:串行传播算法中,初始化变量集合 Q 的时间代价为 O(n)(算法 1 第 2 行、第 3 行).对于 x∈scp(c),每当
一个值(x,a)被删除后,约束 c 会被执行一次维持 GAC 的串行过滤算法,那么约束集 C 中的所有约束被执行串行
过滤算法的总次数最多为 er max d max (算法 1 第 7 行).而执行一次串行过滤算法的时间代价为 O(T)(算法 1 第 8 行),
将串行过滤算法返回的变量集并入 Q 的时间代价为 O(r max )(算法 1 第 11 行、第 12 行),并且其他所有语句的时
间代价均为 O(1),所以串行传播模式的总体时间代价为 O(n+er max d max (T+r max )).又因为 n=O(er max ),且 T>>r max ,故
维持表约束网络 GAC 的串行传播模式的最坏时间复杂度为 O(er max d max T).证毕. □

3 并行传播模式

在本节中,我们提出了维持表约束网络 TGAC 的并行传播模式,它同样由并行传播算法和并行过滤算法两
部分组成.之后,我们分析了并行传播模式的相关性质.
3.1 并行传播算法
在并行传播模式中,我们引入了一些新的数据结构.
• 约束位标识 tableMask:由 e 个位组成的位向量,用以标记需要执行并行过滤算法的表约束,在并行传播
模式中是被动态更新的.其第 i 个位用 tableMask[c i ]表示,tableMask[c i ]为 1b 当且仅当约束 c i 需要被执
行并行过滤算法;
• 位订阅 bitSbp(x):由 e 个位组成的位向量,与变量 x 的约束订阅集 sbp(x)相对应,第 i 个位用 bitSbp(x)[c i ]
表示,bitSbp(x)[c i ]为 1b 当且仅当 x∈scp(c i ).
通过 tableMask:=tableMask|bitSbp(x)可将 bitSbp(x)提交至 tableMask 上.
例 3:约束网络 N 的约束集 C={c 1 ,c 2 ,...,c 8 },变量 x 和 y 的约束订阅集分别为 sbp(x)={c 4 ,c 8 }和 sbp(y)={c 1 ,c 8 },
相应的位订阅 bitSbp(x)和 bitSbp(y)如图 2 所示.约束位标识 tableMask 初始化为 0(全部位均为 0b),将 bitSbp(x)