Page 207 - 《软件学报》2021年第11期

王震 等:优化简单表缩减算法求解因子分解编码实例 3533

定义 5(因子变量). 根据两个约束之间的共同变量生成的变量是因子变量.
定义 6(原始约束). 约束中的平凡变量被替换成相应的因子变量,并且对应的元组发生改变,这样的约束是
原始约束.
定义 7(附加约束). 由一个因子变量和它对应的平凡变量所组成的约束是附加约束.
例 1:假设一个约束网络 N=(X,C)如图 2(a)所示,其中,X={x,y,u,v,w},D(x)=D(y)={0,1},D(u)=D(v)=D(w)={0},
C={c 1 ,c 2 ,c 3 }.此约束网络经 FDE 编码后形成新的约束网络 N′=(X′,C′)如图 2(b)所示,其中,X′={x,y,u,v,w,f},D(x)=
′′ ′
D(y)={0,1},D(u)=D(v)=D(w)={0},D(f)={0,1,2,3},且 C′ = {, , , }c c c c f .在约束网络 N′中,x,y,u,v 和 w 是平凡变量,f
1
3
2
′′
是由平凡变量 x 和 y 生成的因子变量, ,cc 和 c′ 是原始约束,c f 是附加约束.在实际的问题中,经 FDE 编码形成的
3
2
1
约束网络的规模会更加庞大.

Fig.2 Original constraint network and its FDE
图 2 原始约束网络和它的 FDE

2.1 附加约束
附加约束涉及到的变量集合 scp 是由两个或两个以上平凡变量和一个因子变量所组成,那么我们可以对平
凡变量和因子变量进行不同的处理.在给出具体算法之前,我们首先介绍算法中涉及的数据结构.
• RSparseBitSet 是 CT 算法使用的数据结构.RSparseBitSet 存储 4 个成员:words 是一个 bit 数组,limit 是
一个存储 words 长度的整型变量,index 是一个存储 words 中非 0 位置的整型数组,mask 是一个用于修
改 words 的 bit 数组.
• support[x,a]是一个静态 bit 数组,长度与 words 相同,用来存储当前约束对变量值(x,a)的 bit 支持.若当前
约束的元组中变量 x 所对应的值为 a,那么 support[x,a]对应的元组 bit 位是 1,否则是 0.
• last 是一个整型数组,last[x]存储变量 x 的论域大小.
• residues 是一个整型数组,residues[x,a]存储对变量值(x,a)最近一次找到的支持索引.
• S val 和 S sup 是临时变量集合,S val 中存储论域改变的变量,S sup 中存储论域大于 1 的变量.这两个集合用于
提升求解的效率.
[5]
算法 1 介绍了为实现 STRFDE add 对 RSparseBitSet 进行扩展新增加的两个方法:intersectWord 和 getWord.
intersectWord 方法使用因子变量来修改 RSparseBitSet 中的 words,参数为因子变量的论域.getWord 方法用来获
取当前 RSparseBitSet 中的 words,返回值是一个 bit 数组.
算法 1. RSparseBitSet.
1. Data: word: Temporary array of long
2. Method intersectWord(value: Array of long):
3. for i←limit down to 0 do
4. offset←index[i]
5. w←words[offset] & value[offset] //bitwise AND
6. if w!=words[offset] then
7. words[offset]←w
8. if w=0 then