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

软件学报 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