基于比特位操作的自适应约束传播算法  

Adaptive propagation algorithm based on bitwise operations

作　　者：王海燕[1,2,3] 郭劲松[1,2] 欧阳丹彤[1,2] 张永刚[1,2] 

机构地区：[1]吉林大学计算机科学与技术学院,长春130012 [2]吉林大学符号计算与知识工程教育部重点实验室,长春130012 [3]吉林师范大学计算机学院,吉林四平136000

出　　处：《吉林大学学报（工学版）》2012年第5期1219-1224,共6页Journal of Jilin University:Engineering and Technology Edition

基　　金：国家自然科学基金项目(61170314,60973089,61133011,61170092,61003101,41172294);吉林省科技发展计划项目(20101501,20100185,201101039);高等学校博士学科点专项科研基金项目(20100061110031);浙江师范大学计算机软件与理论省级重中之重学科开放基金项目(ZSDZZZZXK12);浙江省自然科学基金项目(Y1100191)

摘　　要：在现有约束传播算法研究的基础上,提出了一种基于比特位操作的自适应约束传播算法AC_MaxRPC_Bitwise。该算法在寻找AC支持及PC支持中引入基于比特位的数据结构,并利用比特位操作加速AC支持和PC证据搜索,从而提高自适应约束传播的效率。对几类典型benchmark问题的测试结果表明,算法AC_MaxRPC_Bitwise在总体性能上明显优于AC及原自适应约束传播算法。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.

关 键 词：人工智能 约束满足问题 自适应约束传播 比特位操作 

分 类 号：TP31[自动化与计算机技术—计算机软件与理论]