基于AC与LmaxRPC的自适应约束传播求解算法  

Adaptive Constraint Propagation Solving Based on AC and LmaxRPC

作　　者：王海燕[1,2,3] 欧阳丹彤[1,2] 张永刚[1,2] 杨明明[1,2] 

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

出　　处：《湖南大学学报（自然科学版）》2013年第7期86-91,共6页Journal of Hunan University:Natural Sciences

基　　金：国家自然科学基金资助项目(61170314;61133011;60973089;61003101;61170092;60973088;41172294);吉林省科技发展计划项目(20101501;20100185;201101039);国家教育部博士点专项基金资助项目(20100061110031)

摘　　要：在现有自适应约束求解方法基础上,提出一种新的自适应约束传播求解算法ADAPTAC-LmaxRPC.该算法能根据约束的不同特性,在传播能力强但开销高的LmaxRPC与传播能力弱却开销低的AC之间自适应地切换进行约束传播.多个Benchmark实例类上的测试实验数据表明,ADAPTAC-LmaxRPC算法有效地平衡了求解效率和算法开销之间的矛盾,大幅度提高了约束求解的效率.On the basis of the current adaptive constraint solving algorithms, this paper proposed a new adaptive constraint propagation solving algorithm ADAPTAckt RPC, which adaptively switches between en- forcing a strong and expensive local consistency LmaxRPC and a weak but more cheaper one AC according to the activity of individual constraints. Test data from several Benchmark instances shows that ADAP ^ACLmaxRPCbalances the contradiction between the constraint solving efficiency and algorithm cost effective- ly, and it improves the efficiency of constraint solving substantially.

关 键 词：人工智能 约束程序 约束满足问题 自适应约束求解 约束传播 

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