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

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

效元组,这通过在第 6 行调用 intersectWord 方法来实现;最后,通过被修改过的平凡变量来更新当前的
有效元组.
• filterDomains 方法利用 RSparseBitSet 来过滤平凡变量的论域,若使某个变量的论域为空,则发生回溯.
• enforceGAC 方法为 STRFDE add 的入口,在调用 filterDomains 之后,只有因子变量 x 的论域没有被过滤,
若有效元组在调用 updateTable 时被平凡变量修改,那么在第 22 行,利用变量的 removeValues 方法根据
当前有效元组来更新因子变量的论域.
2.2 原始约束
原始约束涉及的变量集合 scp 由 n 个平凡变量和 m 个因子变量组成,其中,n 和 m 满足 n≥0,m≥0 且 n+m≥1.
原始约束中涉及到的因子变量与附加约束中的因子变量不同,这些因子变量的论域与原始约束的元组不是一
一对应的,因此不能使用元组直接更新变量的论域.如前所述,因子变量的论域大小等于附加约束的元组个数,
因此,在原始约束中对因子变量的每个值都构造一个 support[x,a]同样可能造成内存溢出问题.为解决这个问题,
我们根据 STRbit 提出了一种新的算法.STRbit 也是当前主流的 GAC 算法,它的效率和 CT 不相上下.在给出具
体算法之前,我们首先介绍算法中涉及的数据结构.
• bitsup[x,a]是一个数组,用来表示当前约束对变量值(x,a)的 bit 支持集合,它只存储不为 0 的 bit 支持.
bitsup[x,a].size 表示当前约束对变量值(x,a)的 bit 支持数量,bitsup[x,a][i]表示第 i 个 bit 支持,
bitsup[x,a][i].ts 表示第 i 个 bit 支持中的索引,bitsup[x,a][i].mask 表示第 i 个 bit 支持对应的 mask 向量.
• val 是一个存储元组 bit 向量的数组.
• del[x]是一个变量值的集合,存储所有已经从变量论域 D(x)中删除但还没有更新当前约束中元组的变
量值.
• residues 是一个整型数组,residues[x,a]存储对变量值(x,a)最近一次找到的支持索引.
ori
算法 3 介绍了 STRFDE 的伪代码,STRbit 中的 LAST 和 restoreL 数据结构有较高的复杂度,可能造成内存
ori
溢出问题,因此 STRFDE 没有使用它们.STRbit 中的 bitsup 只存储非 0 的 bit 支持,所以每个 bitsup[x,a]的长度
可能是不同的,它的长度在算法初始化时被确定.因子变量的变量值越多,相对应的每个变量值的 bit 支持数量
则越少,因此,使用 bitsup 会大幅度地减少内存占用.在算法中,我们使用 residues 去存储变量值最近一次找到的
bit 支持索引,若此支持仍然有效,就不必去遍历 bitsup.
ori
算法 3. STRFDE .
1. Data: scp: array of variables
2. Method deleteInvalidTuple(⋅):
3. foreach x∈scp do
4. foreach a∈del[x] do
5. for i←bitsup[x,a].size−1 down to 0 do
6. index←bitsup[x,a][i].ts
7. u←bitsup[x,a][i].mask & val[index]
8. if u!=0 then
9. val[index]←(¬u) & val[index]
10. del[x].clear(⋅):
11. Method searchSupport(⋅):
12. foreach x∈scp do
13. foreach a∈D(x) do
14. now←residues[x,a]
15. index←bitsup[x,a][now].ts
16. if bitsup[x,a][i].mask & val[index]=0 then