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

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

ori
0 的 bit 支持,而 CT 的 support 存储所有的 bit 元组,所以 STRFDE 的实际空间复杂度要小于 CT.对于 STRbit
来说,STRbit 有两个额外的数据结构 LAST 和 restoreL.LAST 的空间复杂度为 O(r o d o +r f d f ),但它在搜索树的每一
ori
层会存储到 restoreL 中,因此,STRFDE 的实际空间复杂度也小于 STRbit.
ori
性质 4. STRFDE 的最坏时间复杂度为 O(r o d o t/w+r f d f t/w).
ori
证明:在不考虑平凡变量和因子变量的情况下,STRFDE 算法中 deleteInvalidTuple 和 searchSupport 的时间
ori
复杂度都是 O(rdt/w),因此,STRFDE 的最坏时间复杂度为 O(r o d o t/w+r f d f t/w).证毕. □
ori
和对性质 3 的分析一样,STRFDE 的实际时间复杂度也是相对较小的.
3 实 验

我们在 http://www.cril.univ-artois.fr/~lecoutre/benchmarks.html 上选取了 13 组存在非平凡相交的实例集,
共有 403 个实例.我们实现并比较了 7 种算法:CT、PW-CT、CT+FDE、STRbit+FDE、STR2+FDE、STRFDE+FDE
ori
ori
和 STRFDE +FDE.其中,CT 是当前广泛使用的 GAC 算法,其他算法为 fPWC 算法.STRFDE +FDE 只用
ori
ori
STRFDE 求解 FDE 实例,而 STRFDE+FDE 则用 STRFDE 和 STRFDE add 分别处理原始约束和附加约束.为了
简化,下文中使用 STRFDE 代替 STRFDE+FDE.我们采用了 dom/ddeg 变量启发式和 min 值启发式.所有算法的
实现基于使用 scala2.12 和 java11 编写的 CP 求解器,测试环境为 Intel Core i7 3.20GHz 处理器、8GB RAM 内
存和 Windows 10 操作系统.我们限定算法的超时时间为 1 800s.
表 1 展示了算法求解每个实例集的平均时间 t(单位为 s)和平均结点个数 n,#表示实例个数;MO 表示算法在
此实例集上发生内存溢出,对应的百分比表示发生内存溢出的实例个数占总实例个数的比例(例如,100%意味
着算法在此实例集的所有实例上都发生内存溢出).表 1 中有背景的字体表示所有算法中最短的求解时间,加粗
字体表示所有 fPWC 算法中最短的求解时间,最后一行给出了每种算法在给定时间内可求解的实例个数.
Table 1 Mean times (s) and nodes for each algorithm
表 1 每种算法的平均时间(秒)和结点数
FDE
Name CT PW-CT ori
CT STRbit STR2 STRFDE STRFDE
aim-50 t 0.040 0.014 0.069 0.077 0.068 0.069 0.062
#=24 n 3 316 98 3 391 3 391 3 391 3 391 3 391
aim-100 t 163.083 5.899 168.612 172.007 170.610 168.028 166.848
#=24 n 9.47M 78 045 4.59M 408M 4.58M 4.90M 4.88M
aim-200 t 1 151.755 541.227 816.262 816.768 814.895 815.118 814.392
#=20 n 31.03M 4.53M 11.16M 10.40M 12.56M 12.84M 14.21M
dubois t 995.286 820.407 740.444 764.879 727.449 720.033 716.390
#=13 n 96.37M 50.38M 62.97M 57.93M 66.35M 68.82M 69.18M
renault t 0.015 4.001 1.072 0.072 0.072 0.061 0.065
#=2 n 101 101 101 101 101 101 101
modifiedRenault t 725.629 147.464 92.209 108.066 100.403 90.781 93.152
#=50 n 22.10M 316 732 945 615 328 602 871 574 954 641 832 858
rand-10-20-10 t 0.031 0.662 0.132 0.017 0.024 0.010 0.017
#=20 n 830 0 0 0 0 0 0
rand-10-60-20 t 17.437 MO MO MO 0.414 0.151 MO
#=50 n 27 624 100% 100% 100% 0 0 50%
rand-3-20-20f t 12.167 469.325 35.546 37.216 67.944 29.708 38.039
#=50 n 115 064 329 61 43 695 43 695 43 695 43 695 43 695
rand-3-20-20 t 24.722 786.030 73.965 75.418 142.138 59.276 75.465
#=50 n 225 814 53 160 87 943 87 943 87 943 87 943 87 943
rand-5-12-12 t 1.000 24.168 MO MO 0.812 0.047 MO
#=50 n 1 043 0 100% 100% 0 0 100%
rand-8-20-5 t 3.860 1 731.243 MO 17.099 17.128 16.614 20.082
#=20 n 86 903 1 912 70% 6 646 6 646 6 646 6 646
travellingSalesman t 25.419 MO 26.478 36.135 41.696 31.165 27.939
#=30 n 52 933 93% 52 933 52 933 52 933 52 933 52 933
Solve 368 283 272 285 386 386 311