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

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

本文共涉及以下 6 种有关位向量的基本操作.
(1) 位赋值操作:将位向量的某个位赋值为 0b 或 1b,如 v[i]:=0b;
(2) 位判等操作:判断位向量的某个位是否为 0b 或 1b,如 v[i]=0b;
(3) 位向量赋值操作:对位向量的整体进行赋值,如 v:=0 是将位向量 v 的每个位均赋值为 0b;又如,v:=v′是
将位向量 v′整体赋值给位向量 v;
(4) 位向量判等操作:判断位向量的整体取值,如 v=0 是判断位向量 v 中每个位是否均为 0b;
(5) 位向量按位或操作:将两个位向量的对应位进行或运算,如 v|v′;
(6) 位向量按位与操作:将两个位向量的对应位进行与运算,如 v&v′.
例 2:位向量 v 和 v′均由 8 个位组成,它们的取值及经过 v:=v&v′操作的结果如图 1 所示.

v 1 1 1 0 1 1 1 0

v′ 1 1 1 1 1 0 1 1

v:ൌv&v′

v 1 1 1 0 1 0 1 0
Fig.1 Bit vectors and their operations
图 1 位向量及其操作

c
在本文的相关算法中,我们用位向量 bitdom(x)和 bitdom (x)分别表示变量 x 的论域 dom(x)和 x 在约束 c 中
c
c
的局部中间论域 dom (x).设 x 的初始论域 D(x)⊆[1,M],那么 bitdom(x)和 bitdom (x)均由 M 个位组成.bitdom(x)[a]
c
c
为 1b 当且仅当 a∈dom(x),bitdom(x)为 0 当且仅当 dom(x)为空.同理,bitdom (x)[a]为 1b 当且仅当 a∈dom (x),
c
c
bitdom (x)为 0 当且仅当 dom (x)为空.
2 串行传播模式
维持表约束网络 GAC 的串行传播模式由串行传播算法和串行过滤算法两部分组成,本节将依次介绍这两
部分算法,并分析串行传播模式的相关性质.
2.1 串行传播算法
求解 CSP 实例的常用方法是回溯搜索,回溯搜索是一种完整方法,它通过系统地探索实例的搜索空间,可找
到全部的解或者证明无解存在.MAC(maintaining arc consistency)算法 [14] 是一种在搜索过程中维持约束网络
GAC 的回溯搜索算法,目前被认为是求解 CSP 实例最有效的完整方法.在 MAC 算法中,当初始化约束网络、一
个变量被赋值或者一个变量被删值时,串行传播算法会被调用执行,以维持约束网络 GAC.
常用的串行传播算法之一是面向变量的串行传播算法 [15,16] ,面向变量是指传播集合中保存引发传播的变
量.针对不同类型的过滤算法,面向变量的串行传播算法会有所不同.我们使用的串行传播算法 [17] 具体见算法 1
和算法 2.
算法 1. serialPropagate(X evt :set of variables):Boolean.
begin
1 Q:=∅
2 for each variable x∈X evt do
3 insert(Q,x)
4 inconsistent:=false
5 while Q≠∅ do
6 pick and delete x from Q
7 for each constraint c∈sbp(x)∧stamp(x)>stamp(c) do