| 改进求解约束满足问题粗粒度弧相容算法 |
| |
| 引用本文： | 李宏博,李占山,王涛.改进求解约束满足问题粗粒度弧相容算法[J].软件学报,2012,23(7):1816-1823. |
| |
| 作者姓名： | 李宏博 李占山 王涛 |
| |
| 作者单位： | 吉林大学计算机科学与技术学院;吉林大学符号计算与知识工程教育部重点实验室;长春工业大学计算机科学与工程学院; |
| |
| 基金项目： | 国家自然科学基金(60773097, 60873148, 60973089); 吉林省自然科学基金(201101039, 20071106, 20080107); 国家教育部博士点专项基金(20100061110031) |
| |
| 摘 要： | 约束满足问题在人工智能领域有着广泛的应用.研究了约束满足问题的粗粒度维持弧相容求解算法,发现在求解过程中,对于指向已赋值变量的弧存在无效的修正检查,证明了这类修正检查是冗余的.提出一种方法避免这类冗余的修正检查,给出改进后的粗粒度弧相容算法的基本框架AC3_frame_ARR,该改进框架可用于改进所有粗粒度弧相容算法.实验结果表明,经过AC3_frame_ARR改进后的算法最多可以节省80%的修正检查次数和40%的求解耗时.
|
| 关 键 词： | 约束满足问题 维持弧相容 粗粒度算法 修正检查 |
| 收稿时间： | 2011/6/29 0:00:00 |
| 修稿时间： | 2011/10/8 0:00:00 |
Improving Coarse-Grained Arc Consistency Algorithms in Solving Constraint Satisfaction Problems |
| |
| LI Hong-Bo,LI Zhan-Shan and WANG Tao.Improving Coarse-Grained Arc Consistency Algorithms in Solving Constraint Satisfaction Problems[J].Journal of Software,2012,23(7):1816-1823. |
| |
| Authors: | LI Hong-Bo LI Zhan-Shan and WANG Tao |
| |
| Affiliation: | College of Computer Science and Technology, Jilin University, Changchun 130012, China;Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun 130012, China;College of Computer Science and Technology, Jilin University, Changchun 130012, China;Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun 130012, China;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. |
| |
| Keywords: | constraint satisfaction problem maintaining arc consistency coarse-grained algorithm revision |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《软件学报》浏览原始摘要信息 |
|
点击此处可从《软件学报》下载全文 |
|
