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

3534 Journal of Software 软件学报 Vol.32, No.11, November 2021

9. index[i]←index[limit]
10. index[limit]←offset
11. limit←limit−1
12. Method getWord(⋅):
13. for i←limit down to 0 do
14. offset←index[i]
15. word[offset]←words[offset]
16. return word
算法 2 介绍了 STRFDE add 的伪代码,省略部分与 CT 算法相同.STRFDE add 是基于 CT 算法的改进算法,由于
附加约束所涉及的最后一个变量为此约束所对应的因子变量 x,且因子变量的论域和约束的元组是一一对应
的,所以因子变量的论域大小|D(x)|等于当前约束的元组数量|rel(c)|,若对每一个 a∈D(x)都构造一个 support[x,a]
而 support[x,a]的长度与 RSparseBitSet 中 words 的长度相等,这样就可能造成内存溢出问题.为了解决这一问题,
我们使用 bitset 来存储因子变量的论域,当因子变量发生改变时,直接使用因子变量的论域来修改约束的元组.
同样地,当约束的元组发生改变时,直接使用 RSparseBitSet 中的 words 来修改因子变量的论域.如此,我们只需要
为每个平凡变量构造 support[x,a].因此,last,support 和 residues 的大小都为|scp|−1.在算法 2 中的第 4 行和第 21
行所使用的 getFactorVariable 方法是用来获取与当前附加约束所对应的因子变量.
算法 2. STRFDE add .
1. Data: scp: array of variables
2. currTable: RSparseBitSet
3. Method updateTable(⋅):
4. x←getFactorVariable(this)
5. if x.change(⋅) then
6. currTab.intersectWord(x.getBitDom(⋅))
val
7. foreach x∈S do
8. …
9. Method filterDomains(⋅):
10. …
11. Method enforceGAC(⋅):
val
12. S ←{x∈scp:|D(x)|!=lastSize[x]}
val
13. foreach x∈S do
14. last[x]←|D(x)|
sup
15. S ←{x∈scp:|D(x)|>1}
16. updateTable(⋅)
17. if currTable.isEmpty(⋅) then
18. return Backtrack
19. filterDomains(⋅)
20. if currTable.change(⋅) then
21. x←getFactorVariable(this)
22. x.removeValues(currTab.getWord(⋅))
STRFDE add 由 3 种方法构成.
• updateTable 方法利用约束所涉及的变量来更新当前的有效元组:首先,获取当前附加约束所对应的因
子变量;然后判断这个变量是否被其他约束修改过,如果被修改过,那么我们需要用它来更新当前的有