软件学报

作者：王震，李哲，李占山

单位：王震，吉林大学计算机科学与技术学院, 吉林 长春 130012;符号计算与知识工程教育部重点实验室(吉林大学), 吉林 长春 13001211,李哲，吉林大学计算机科学与技术学院, 吉林 长春 130012;符号计算与知识工程教育部重点实验室(吉林大学), 吉林 长春 13001202,李占山，吉林大学计算机科学与技术学院, 吉林 长春 130012;符号计算与知识工程教育部重点实验室(吉林大学), 吉林 长春 13001203

关键词：约束程序;孤相容;表约束;简单表缩减算法;因子分解编码

基金：国家自然科学基金（61802056）；吉林省自然科学基金（20180101043JC）；吉林省发展和改革委员会产业技术研究与开发项目（2019C053-9）；中国科学院太空应用重点实验室开放基金（LSU-KFJJ-2019-08）

表约束在约束程序（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的优势，在保证求解效率的同时，使占用的内存尽可能小.实验结果表明，在许多存在非平凡相交的实例上，该算法是有竞争力的.

来源：2021年第11期

《软件学报》期刊编辑部

查看软件学报杂志2021年第11期