| 摘要: |
| 约束满足问题在人工智能领域有着广泛的应用.研究了约束满足问题的粗粒度维持弧相容求解算法,发现在求解过程中,对于指向已赋值变量的弧存在无效的修正检查,证明了这类修正检查是冗余的.提出一种方法避免这类冗余的修正检查,给出改进后的粗粒度弧相容算法的基本框架AC3_frame_ARR,该改进框架可用于改进所有粗粒度弧相容算法.实验结果表明,经过AC3_frame_ARR 改进后的算法最多可以节省80%的修正检查次数和40%的求解耗时. |
| 关键词: 约束满足问题 维持弧相容 粗粒度算法 修正检查 |
| DOI：10.3724/SP.J.1001.2012.04129 |
| 分类号: |
| 基金项目:国家自然科学基金(60773097, 60873148, 60973089); 吉林省自然科学基金(201101039, 20071106, 20080107); 国家教育部博士点专项基金(20100061110031) |
|
| Improving Coarse-Grained Arc Consistency Algorithms in Solving Constraint Satisfaction Problems |
|
LI Hong-Bo1,2, LI Zhan-Shan1,2, WANG Tao3
|
|
1.College of Computer Science and Technology, Jilin University, Changchun 130012, China;2.Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun 130012, China;3.School of Computer Science and Engineering, Changchun University of Technology, Changchun 130012, China
|
| Abstract: |
| Constraint satisfaction problems have been widely investigated in artificial intelligence area. This paper investigates whether the coarse-grained maintaining arc is consistent, which is used to solve CSPs. The study has found that during the search for a solution, there are ineffective revisions, which revise the arcs that point to assigned variables. This study has proved that such revisions are redundant and proposed a method to avoid such redundant revisions. The paper gives the improved basic frame for the coarse-grained arc consistency algorithms, named AC3_frame_ARR. The new frame can be applied to improve all the coarse-grained AC algorithms. The experimental results show that the improved algorithms can save at most 80% revisions and 40% CPU time. |
| Key words: constraint satisfaction problem maintaining arc consistency coarse-grained algorithm revision |
