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

• 作者: 孙吉贵 张永刚 朱兴军 李莹
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 约束满足问题 弧相容技术 singleton弧相容 pre-弧相容
• 年，卷（期）: 2008,（6）
• 所属期刊栏目: 研究论文与技术报告
• 页码范围: 919-926
• 页数: 8页
• 分类号: TP18
• 字数: 6807字
• 语种: 中文
• DOI: 10.3321/j.issn:0254-4164.2008.06.004

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	孙吉贵	吉林大学计算机科学与技术学院	134	2984	21.0	52.0
5	朱兴军	吉林大学计算机科学与技术学院	5	52	3.0	5.0
9	张永刚	吉林大学计算机科学与技术学院	35	296	9.0	16.0
13	李莹	吉林大学计算机科学与技术学院	48	236	10.0	14.0