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

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