负表约束的简单表缩减广泛弧相容算法

来源：软件学报杂志2016年第11期北京时间：

作者：李宏博,梁艳春,李占山

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

摘要：广泛弧相容算法（generalized arc consistency，简称GAC），是求解约束满足问题的核心方法.表约束理论上可以表示所有约束关系，在过去10年中，有很多应用于表约束的广泛弧相容算法被提出来.在这些算法中，表缩减算法的效率非常高.但是目前的表缩减算法只能应用于正表约束，无法直接应用于负表约束.首先，提出一种表缩减算法STR-N，可以直接应用于负表约束；然后，给出了STR-N的两个改进版本STR-N2和STR-NIC.实验结果显示，STR-N算法在负表约束上的求解效率具有明显的优势.

关键词：约束满足问题;广泛弧相容;简单表缩减;负表约束

基金资助：国家自然科学基金（61472158，61272207）；吉林省科技计划（20140101200JC）