一种新的基于完全独立相容性的预处理技术

• 作者: 孙吉贵 张永刚 朱兴军 李莹
• 来源期刊: 自动化学报
• 学科: 工学
• 关键词: 约束满足问题 预处理技术 完全独立相容性 分治策略
• 年，卷（期）: 2009,（1）
• 所属期刊栏目: 论文报告
• 页码范围: 71-76
• 页数: 6页
• 分类号: TP18
• 字数: 5665字
• 语种: 中文
• DOI: 10.3724/SP.J.1004.2009.00071

摘要

研究了求解约束满足问题(Constraint satisfaction problem,CSP)中的预处理技术.首先提出了子论域上的完全独立相容性(Entirety singleton consistency,ESC)概念和相应算法,分析并证明了算法的复杂性和正确性,而后对其两条重要性质进行了详细证明.基于此概念和性质,提出了一种基于完全独立相容性的预处理算法:SAC-ESC算法,并给出了正确性证明.最后,本文采用分治思想,根据不同问题的论域自适应地合理划分其子论域.实验结果表明,对于随机问题、鸽巢问题、N皇后问题和基准用例,算法SAC-ESC的执行效率大约是目前流行算法SAC-SDS和SAC-3的3～20倍.

作者信息

序号	姓名	单位	发文数	被引次数	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