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

陈佳楠 等:基于多核 CPU 的表约束并行传播模式研究 2773

8 Y evt :=enforceGAC(c)
9 if inconsistent then
10 return false
11 for each variable y∈Y evt do
12 insert(Q,y)
13 time:=time+1
14 stamp(c):=time
15 return true
end
算法 2. insert(Q:set of variables,x:variable).
begin
1 Q:=Q∪{x}
2 time:=time+1
3 stamp(x):=time
end
在算法 1 中,Q 是一个变量集合,保存引发传播的变量,即:当一个变量的论域被删值时,该变量会被添加至 Q
中.串行传播算法通过使用时间戳来避免不必要的工作,时间戳是一个值,表示某个事件发生的时间.变量 x 的时
间戳 stamp(x)表示最近一次从 dom(x)中删除值的时间,约束 c 的时间戳 stamp(c)表示最近一次在 c 上维持 GAC
的时间.时间通过计数器 time 来模拟.time,stamp(x)和 stamp(c)均被初始化为 0.
算法 1 的传入参数 X evt 是引发初始传播的变量集合,其中的变量会被添加至 Q 中.算法 1 第 6 行从 Q 中选
出一个变量 x 后,对包含 x 的每个约束 c,如果 stamp(x)大于 stamp(c),算法 1 第 8 行会执行在 c 上维持 GAC 的串
行过滤算法.串行过滤算法会返回由被删值的变量组成的集合,并且如果有一个变量的论域被删空,串行过滤算
法会将不相容标识 inconsistent 置为 true,之后,inconsistent 会在算法 1 第 9 行被识别出,这表明传播失败,当前表
约束网络无解,MAC 算法发生回溯.当 Q 中的所有变量均被选出传播后,并且传播期间没有变量的论域被删空,
这表明传播成功,当前表约束网络是 GAC 的,MAC 算法继续搜索.
2.2 串行过滤算法
如前文所述,维持表约束 GAC 的串行过滤算法研究已经公布了大量成果,它们的设计实现虽然有所不同,
但主要由更新表(算法 4)和过滤论域(算法 5)两部分组成.我们总结了它们的共同之处,具体见算法 3~算法 5.
算法 3. enforceGAC(c):set of variables.
begin
1 updateTable(c)
2 return filterDomains(c)
end
算法 4. updateTable(c).
begin
1 for each τ∈rel(c) do
2 for each x∈scp(c) do
3 if bitdom(x)[τ[x]]=0b then
4 rel(c):=rel(c)\{τ}
5 break
end