| 一种改进的双向singleton弧相容算法 |
| |
| 引用本文： | 刘春晖,朱兴军,孙吉贵,姜珊珊. 一种改进的双向singleton弧相容算法[J]. 吉林大学学报(工学版), 2008, 38(3): 666-0670 |
| |
| 作者姓名： | 刘春晖 朱兴军 孙吉贵 姜珊珊 |
| |
| 作者单位： | 吉林大学计算机科学与技术学院,符号计算与知识工程教育部重点实验室,长春,130012;吉林大学计算机科学与技术学院,符号计算与知识工程教育部重点实验室,长春,130012;吉林大学计算机科学与技术学院,符号计算与知识工程教育部重点实验室,长春,130012;吉林大学计算机科学与技术学院,符号计算与知识工程教育部重点实验室,长春,130012 |
| |
| 基金项目： | 国家自然科学基金 , 教育部跨世纪优秀人才培养计划 |
| |
| 摘 要： | 在现有相容性算法研究的基础上,提出了一种在约束网络中确立双向singleton弧相容的新算法——BiSAC-2,并给出了其正确性和完备性证明。该算法与原有算法BiSAC-1具有相同的化简问题能力,但BiSAC-2能够减少弧相容维护的次数,避免冗余约束传播过程的产生,从而可以快速地到达稳定点,进而实现高效的目的。对随机约束满足问题的测试结果表明,算法BiSAC-2比原始算法BiSAC-1具有更明显的性能优势。
|
| 关 键 词： | 人工智能 约束满足问题 相容性技术 双向singleton弧相容 |
| 文章编号： | 1671-5497(2008)03-0666-05 |
| 收稿时间： | 2007-06-13 |
| 修稿时间： | 2007-12-13 |
Improved bidirectional singleton arc consistency algorithm |
| |
| Liu Chun-hui,Zhu Xing-jun,Sun Ji-gui,Jiang Shan-shan. Improved bidirectional singleton arc consistency algorithm[J]. Journal of Jilin University:Eng and Technol Ed, 2008, 38(3): 666-0670 |
| |
| Authors: | Liu Chun-hui Zhu Xing-jun Sun Ji-gui Jiang Shan-shan |
| |
| Affiliation: | College of Computer Science and Technology, Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun 130012, China |
| |
| Abstract: | The existing notions and techniques of consistency algorithm were further investigated.Then a new algorithm——BiSAC-2 was proposed to enforce the bidirectional singleton arc consistency in constraint network.The soundness and completeness of the algorithm were proved.BiSAC-2 has the same ability to simplify the problem as that of the conventional BiSAC-1.However the number for maintaining the arc consistency is reduced and the fix-point can be reached much quickly,hence the efficiency can be improved.Experiments on random CSPs show that the new algorithm,BiSAC-2,needs much less time compared with the conventional algorithm BiSAC-1. |
| |
| Keywords: | artificial intelligence constraint satisfaction problem consistency technique bidirectional singleton arc consistency |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《吉林大学学报(工学版)》浏览原始摘要信息 |
|
点击此处可从《吉林大学学报(工学版)》下载全文 |
|
