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

王震  等:优化简单表缩减算法求解因子分解编码实例                                                       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
   206   207   208   209   210   211   212   213   214   215   216