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

软件学报 ISSN 1000-9825, CODEN RUXUEW                                       E-mail: jos@iscas.ac.cn
                 Journal of Software,2021,32(11):3530−3540 [doi: 10.13328/j.cnki.jos.006094]   http://www.jos.org.cn
                 ©中国科学院软件研究所版权所有.                                                         Tel: +86-10-62562563


                                                                       ∗
                 优化简单表缩减算法求解因子分解编码实例

                               1,2
                      1,2
                 王   震 ,   李   哲 ,   李占山  1,2
                 1
                 (吉林大学  计算机科学与技术学院,吉林  长春  130012)
                 2
                 (符号计算与知识工程教育部重点实验室(吉林大学),吉林  长春   130012)
                 通讯作者:  李占山, E-mail: zslizsli@163.com

                 摘   要:  表约束在约束程序(constraint programming,简称 CP)中被广泛研究.目前,求解表约束问题效率最高的算
                 法是 CT(compact-table)和 STRbit(simple tabular reduction bit).它们在搜索过程中维持广义弧相容(generalized arc
                 consistency,简称 GAC).完全成对相容(full pairwise consistency,简称 fPWC)是一种强于 GAC 的相容性关系,目前,实
                 现 fPWC 效率最高的算法是 PW-CT,但是它无法直接在通用的求解器上实现.因子分解编码(factor-decomposition
                 encoding,简称 FDE)是实现 fPWC 的一种编码方式,通常和简单表缩减(STR)算法一起来使用.当前效率最高的 STR
                 算法使用了 bitset 的数据结构,用这些算法来求解 FDE 实例可能会造成内存溢出.提出了 STRFDE 算法——一种使
                 用 bitset 结构来求解 FDE 实例的方法.它结合了 CT 和 STRbit 的优势,在保证求解效率的同时,使占用的内存尽可能
                 小.实验结果表明,在许多存在非平凡相交的实例上,该算法是有竞争力的.
                 关键词:  约束程序;孤相容;表约束;简单表缩减算法;因子分解编码
                 中图法分类号: TP18

                 中文引用格式:  王震,李哲,李占山.优化简单表缩减算法求解因子分解编码实例.软件学报,2021,32(11):3530−3540.  http://
                 www.jos.org.cn/1000-9825/6094.htm
                 英文引用格式: Wang Z, Li Z, Li ZS. Optimizing simple tabular reduction algorithm for factor-decomposition encoding instances.
                 Ruan Jian Xue Bao/Journal of Software, 2021,32(11):3530−3540 (in Chinese). http://www.jos.org.cn/1000-9825/6094.htm

                 Optimizing Simple  Tabular Reduction Algorithm  for Factor-decomposition Encoding
                 Instances

                          1,2
                                   1,2
                 WANG Zhen ,  LI Zhe ,   LI Zhan-Shan 1,2
                 1 (School of Computer Science and Technology, Jilin University, Changchun 130012, China)
                 2 (Key Laboratory of Symbolic Computation and Knowledge Engineering (Jilin University), Ministry of Education, Changchun 130012,
                  China)

                 Abstract:    Table constraints are widely studied in constraint programming (CP). At present, the most efficient algorithms for solving
                 table constraint problems are compact-table (CT) and simple tabular reduction bit (STRbit), which maintain generalized arc consistency
                 (GAC) during the search process. Full pairwise  consistency (fPWC) is  a  consistency that is  stronger than  GAC.  The  most  efficient
                 algorithm for maintaining fPWC is PW-CT which is difficult to implement in general solver. Factor-decomposition encoding (FDE) is an
                 encoding method that implements fPWC and is usually used together with STR. The current STR algorithms that use bitset may cause
                 memory overflow issues to solve FDE instances. This study proposes STRFDE, a new algorithm using bitset for solving FDE instances. It


                   ∗  基金项目:  国家自然科学基金(61802056);  吉林省自然科学基金(20180101043JC);  吉林省发展和改革委员会产业技术研究与
                 开发项目(2019C053-9);  中国科学院太空应用重点实验室开放基金(LSU-KFJJ-2019-08)
                      Foundation item: National Natural Science Foundation of China (61802056); Natural Science Foundation of Jilin Province (2018010
                 1043JC); Industrial Technology Research and Development Project of Jilin Development and Reform Commission (2019C053-9); Open
                 Research Fund of Key Laboratory of Space Utilization, Chinese Academy of Sciences (LSU-KFJJ-2019-08)
                      收稿时间: 2020-01-04;  修改时间: 2020-05-01;  采用时间: 2020-06-01
   199   200   201   202   203   204   205   206   207   208   209