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

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

表 2 给出了算法在求解实例集时所占用的平均内存(以 Mb 为单位),百分比表示内存溢出的比例.通过分析,
我们可以得出,在所有的实例上,CT+FDE 与 STRbit+FDE 均比 STRFDE 占用更多的内存,有的甚至是 STRFDE
的数十倍;与 STR2+FDE 相比,STRFDE 内存增加的原因是使用了 bitset 的数据结构.这表明,STRFDE 在保持效
率的同时尽可能地减少了内存占用.STRbit 在求解一些实例时占用内存高于其他算法的原因是,其使用了 LAST
ori
和 restoreL 数据结构.STRFDE 在约束涉及的元组较少时占用内存略优于 STRFDE,但整体上还是 STRFDE 效
果更好.
Table 2 Mean memory for each algorithm (Mb)
表 2 每种算法的平均内存 (Mb)
FDE
name # CT PW-CT ori
CT STRbit STR2 STRFDE STRFDE
aim-50 24 0.44 5.24 1.98 5.50 0.83 1.17 1.16
aim-100 24 1.41 19.32 6.40 18.42 2.64 3.64 3.61
aim-200 20 4.11 51.72 12.69 35.95 5.53 8.40 8.29
dubois 13 0.74 5.31 0.77 1.70 0.46 0.73 0.73
renault 2 5.17 234.93 1 450.96 307.66 4.67 26.67 35.72
modifiedRenault 50 5.75 266.06 1 455.73 378.53 5.71 29.17 38.65
rand-10-20-10 20 0.77 16.75 648.98 75.82 1.34 14.90 26.81
rand-10-60-20 50 48.42 100% 100% 100% 79.22 612.41 50%
rand-3-20-20f 50 1.84 38.35 19.53 25.37 1.05 6.88 8.20
rand-3-20-20 50 1.84 38.35 19.53 25.37 1.05 6.88 8.20
rand-5-12-12 50 22.76 346.20 100% 100% 261.54 908.14 100%
rand-8-20-5 20 10.56 184.47 70% 280.94 7.50 128.02 136.77
travellingSalesman 30 59.73 93% 59.73 42.90 2.20 24.24 24.24

4 总 结

本文提出了一种结合 FDE 方法一起维持 fPWC 的表约束求解算法 STRFDE,它采用不同的方法来处理不
同的约束.STRFDE 结合了 CT 和 STRbit 的优点,在保证求解效率的同时,使占用的内存尽可能小.实验表明,
STRFDE+FDE 在大多数情况下是维持 fPWC 最快的算法.当然,STRFDE 也有一些缺点:它只适用于经过 FDE
处理后的约束网络,不能应用在原约束网络上.下一步,我们准备继续完善 STRFDE 算法,并将它在主流求解器上
实现.
References:
[1] Ullmann JR. Partition search for non-binary constraint satisfaction. Information Sciences, 2007,177(18):3639−3678.
[2] Lecoutre C. STR2: Optimized simple tabular reduction for table constraints. Constraints, 2011,16(4):341−371.
[3] Lecoutre C, Likitvivatanavong C, Yap RHC. STR3: A path-optimal filtering algorithm for table constraints. Artificial Intelligence,
2015,220:1−27.
[4] Wang R, Xia W, Yap RHC, Li Z. Optimizing simple tabular reduction with a bitwise representation. In: Proc. of the IJCAI. 2016.
787−795.
[5] Demeulenaere J, Hartert R, Lecoutre C, Perez G, Perron L, Régin JC, Schaus P. Compact-table: Efficiently filtering table
constraints with reversible sparse bit-sets. In: Proc. of the Int’l Conf. on Principles and Practice of Constraint Programming. Cham:
Springer-Verlag, 2016. 207−223.
[6] Li HB, Liang YC, Li ZS. Simple tabular reduction for generalized arc consistency on negative table constraints. Ruan Jian Xue
Bao/Journal of Software, 2016,27(11):2701−2711 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4847.htm
[doi: 10.13328/j.cnki.jos.004874]
[7] Yang MQ, Li ZS, Li Z. Optimizing MDDc and STR3 for solving constraint satisfaction problem. Ruan Jian Xue Bao/Journal of
Software, 2017,28(12):3156−3166 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/5242.htm [doi: 10.13328/j.
cnki.jos.005242]
[8] Yang MQ, Li ZS, Zhang JC. Simple tabular reduction algorithm based on time-stamp mechanism. Ruan Jian Xue Bao/Journal of
Software, 2019,30(11):3355−3363 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/5559.htm [doi: 10.13328/j.
cnki.jos.005559]