| 基于比特位操作的自适应约束传播算法 |
| |
| 引用本文： | 王海燕,郭劲松,欧阳丹彤,张永刚.基于比特位操作的自适应约束传播算法[J].吉林大学学报(工学版),2012,42(5):1219-1224. |
| |
| 作者姓名： | 王海燕 郭劲松 欧阳丹彤 张永刚 |
| |
| 作者单位： | 1. 吉林大学计算机科学与技术学院,长春130012 吉林大学符号计算与知识工程教育部重点实验室,长春130012 吉林师范大学计算机学院,吉林四平136000
2. 吉林大学计算机科学与技术学院,长春130012 吉林大学符号计算与知识工程教育部重点实验室,长春130012 |
| |
| 基金项目： | 国家自然科学基金项目，吉林省科技发展计划项目，高等学校博士学科点专项科研基金项目，浙江师范大学计算机软件与理论省级重中之重学科开放基金项目，浙江省自然科学基金项目 |
| |
| 摘 要： | 在现有约束传播算法研究的基础上,提出了一种基于比特位操作的自适应约束传播算法AC_MaxRPC_Bitwise。该算法在寻找AC支持及PC支持中引入基于比特位的数据结构,并利用比特位操作加速AC支持和PC证据搜索,从而提高自适应约束传播的效率。对几类典型benchmark问题的测试结果表明,算法AC_MaxRPC_Bitwise在总体性能上明显优于AC及原自适应约束传播算法。
|
| 关 键 词： | 人工智能 约束满足问题 自适应约束传播 比特位操作 |
Adaptive propagation algorithm based on bitwise operations |
| |
| WANG Hai-yan,GUO Jin-song,OUYANG Dan-tong,ZHANG Yong-gang.Adaptive propagation algorithm based on bitwise operations[J].Journal of Jilin University:Eng and Technol Ed,2012,42(5):1219-1224. |
| |
| Authors: | WANG Hai-yan GUO Jin-song OUYANG Dan-tong ZHANG Yong-gang |
| |
| Affiliation: | 1,2(1.College of Computer Science and Technology,Jilin University,Changchun 130012,China;2.Key Laboratory of Symbolic Computation and Knowledge Engineering for Ministry of Education,Jilin University,Changchun 130012,China;3.College of Computer,Jilin Normal University,Siping 136000,China) |
| |
| Abstract: | On the basis of the research of the constraint propagation algorithm,an adaptive constraint propagation algorithm,AC_MaxRPC_Bitwise,is proposed,which is based on bitwise operations.The proposed algorithm has several advantages in improving the efficiency of adaptive constraint propagation method.First,it introduces bitwise method to represent the data structure while looking for AC support and PC support.Second,it uses bitwise operation to speed up the searching process of AC support and PC witness.Experiments were conducted on a few typical benchmark problems.Results show that the improved algorithm AC_MaxRPC_Bitwise whelms AC and other constraint propagation algorithm in overall performance. |
| |
| Keywords: | artificial intelligence constraint satisfaction problem adaptive constraint propagation bitwise operations |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
