| 弧相容算法性能比较 |
| |
| 引用本文： | 徐均哲,孙吉贵,张永刚.弧相容算法性能比较[J].吉林大学学报(信息科学版),2007,25(2):177-182. |
| |
| 作者姓名： | 徐均哲 孙吉贵 张永刚 |
| |
| 作者单位： | 吉林大学,计算机科学与技术学院,长春,130012;吉林大学,符号计算与知识工程教育部重点实验室,长春,130012;吉林大学,计算机科学与技术学院,长春,130012;吉林大学,符号计算与知识工程教育部重点实验室,长春,130012;吉林大学,计算机科学与技术学院,长春,130012;吉林大学,符号计算与知识工程教育部重点实验室,长春,130012 |
| |
| 基金项目： | 国家自然科学基金
,
高等学校博士学科点专项科研项目
,
吉林省发展计划基金 |
| |
| 摘 要： | 为了化简约束满足问题的规模、有效地处理大规模难解问题,从求解算法的角度研究弧相容技术。分析讨论了8种弧相容算法各自的优势和特点。在“明月”约束求解平台上针对随机约束满足问题,对该系列弧相容算法的性能进行了测试。实验结果表明,无论是在搜索之前还是搜索过程中,AC-2001(AC-3.1)都比其他算法表现出更优异的性能。
|
| 关 键 词： | 约束满足问题 约束求解 弧相容 相容性检查 |
| 文章编号： | 1671-5896(2007)02-0177-06 |
| 修稿时间： | 2006年9月29日 |
Performance Comparison of Arc Consistency Algorithms |
| |
| XU Jun-zhe,SUN Ji-gui,ZHANG Yong-gang.Performance Comparison of Arc Consistency Algorithms[J].Journal of Jilin University:Information Sci Ed,2007,25(2):177-182. |
| |
| Authors: | XU Jun-zhe SUN Ji-gui ZHANG Yong-gang |
| |
| Abstract: | In order to reduce CSPs(Constraint Satisfaction Problems) to deal with large and hard problems effectively,we study arc consistency techniques from an algorithm point of view.We analysis and discuss each the advantages and characteristics of all the eight kinds of arc consistency algorithms.We test all the algorithms on random generate problems and examine their performance based on the "Mingyue" constraint solving platform.The results show that AC-2001(AC-3.1) is better than other algorithms on both before search and during search. |
| |
| Keywords: | constraint satisfaction problems(CSPs) constraint solving arc consistency(AC) consistency checks |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
