软件学报

作者：李哲，于哲舟，李占山

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

关键词：约束规划;并行约束传播;相容性算法;简单表缩减算法

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

约束规划(constraint programming, CP)是表示和求解组合问题的经典范式之一. 扩展约束(extensional constraint)或称表约束(table constraint)是约束规划中最为常见的约束类型. 绝大多数约束规划问题都可以用表约束表达. 在问题求解时, 相容性算法用于缩减搜索空间. 目前, 最为高效的表约束相容性算法是简单表约缩减(simple table reduction, STR)算法簇, 如Compact-Table (CT)和STRbit算法. 它们在搜索过程中维持广义弧相容(generalized arc consistency, GAC). 此外, 完全成对相容性(full pairwise consistency, fPWC)是一种比GAC剪枝能力更强的相容性. 最为高效的维持fPWC算法是PW-CT算法. 多年来, 人们提出了多种表约束相容性算法来提高剪枝能力和执行效率. 因子分解编码(factor-decomposition encoding, FDE)通过对平凡问题重新编码. 它一定程度地扩大了问题模型, 使在新的问题上维持相对较弱的GAC等价于在原问题上维持fPWC. 目前, FDE的合适STR算法是STRFDE和STR2, 而不是CT. 这是由于CT算法可能产生内存溢出问题. 在维持相容性算法的过程中, 需要将迭代地调用各个约束执行其相容性算法过滤搜索空间, 这个过程称为约束传播. 动态提交方案是一个并行约束传播框架, 可以并行地调度约束执行传播算法. 它在大规模问题中, 改进效果尤为明显. 改进STRFDE和动态提交传播算法. 针对FDE提出了PSTRFDE算法. PSTRFDE可以嵌入到动态提交方案中, 进一步提高了约束规划问题的求解效率. 大量的实验表明, PSTRFDE与CT和STRbit相比, 可以减少内存占用; 与STRFDE和STR2相比, 可以提高算法的效率. 所作工作充分说明了PSTRFDE是FDE上最为高效的过滤算法.

来源：2023年第9期

《软件学报》期刊编辑部

查看软件学报杂志2023年第9期