一种基于预处理技术的约束满足问题求解算法

摘要：

相容性技术作为约束满足问题的一种有效求解技术,不论是在求解前的预处理过程中,还是在搜索过程中,都扮演着极为重要的角色.文中对预处理阶段的相容性技术进行改进和信息抽取,提出两种应用于搜索过程中的新算法Pre-AC和Pre-AC*,并嵌入到BT框架中,形成新的搜索算法BT+MPAC和BT+MPAC*,给出了其正确性证明,通过复杂性分析得到Pre-AC和Pre-AC*的时间复杂度分别是O(nd)和O(ed2),明显低于目前最流行的弧相容技术的时间复杂度O(ed3).实验测试结果表明:对于不同类别的用例,新算法的执行效率是弧相容维护算法的2～50倍.

关键词：约束满足问题、弧相容技术、singleton弧相容、pre-弧相容

所属期刊栏目：31

分类号：TP18(自动化基础理论)

资助基金：国家自然科学基金项目"扩展规则推理方法研究"60773097

在线出版日期：2008-08-19（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：919-926