摘要
在现有约束传播算法研究的基础上,提出了一种基于比特位操作的自适应约束传播算法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.
出处
《吉林大学学报（工学版）》
EI
CAS
CSCD
北大核心
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)
关键词
人工智能
约束满足问题
自适应约束传播
比特位操作
artificial intelligence
constraint satisfaction problem
adaptive constraint propagation
bitwise operations
