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

• 作者: 李占山 李宏博 梁艳春
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 约束满足问题 广泛弧相容 简单表缩减 负表约束
• 年，卷（期）: 2016,（11）
• 所属期刊栏目: 模式识别与人工智能
• 页码范围: 2701-2711
• 页数: 11页
• 分类号: TP181
• 字数: 9110字
• 语种: 中文
• DOI: 10.13328/j.cnki.jos.004874

摘要

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