《计算机学报》文章摘要   全文下载
文章题目	一种基于预处理技术的约束满足问题求解算法
作者	孙吉贵1),2) 朱兴军1),2) 张永刚1),2) 李莹1),2)
作者单位	1)(吉林大学计算机科学与技术学院 长春 130012) 2)(吉林大学符号计算与知识工程教育部重点实验室 长春 130012)
发表年份	2008
发表月份	6期(919—926)
文章摘要	摘要 相容性技术作为约束满足问题的一种有效求解技术，不论是在求解前的预处理过程中，还是在搜索过程中，都扮演着极为重要的角色.文中对预处理阶段的相容性技术进行改进和信息抽取，提出两种应用于搜索过程中的新算法Pre-AC和Pre-AC*，并嵌入到BT框架中，形成新的搜索算法BT+MPAC和BT+MPAC*，给出了其正确性证明，通过复杂性分析得到Pre-AC和Pre-AC*的时间复杂度分别是O(nd)和O(ed2),明显低于目前最流行的弧相容技术的时间复杂度O(ed3).实验测试结果表明：对于不同类别的用例，新算法的执行效率是弧相容维护算法的2~50倍. 关键词：约束满足问题；弧相容技术；singleton弧相容；pre-弧相容