基于成功回溯的约束推理技术  

Reasoning from successful backtracking in constraint programming

作　　者：王涛[1] 张乾[2,3] 李占山[2,3] 张良[2,3] 

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

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

基　　金：国家自然科学基金项目(61170314;61272208);吉林省科技发展计划项目(20140101200JC;20071106);教育部高等学校博士学科点专项科研基金项目(20100061110031)

摘　　要：提出了基于成功回溯的约束推理技术及其相应的约束求解算法MAC_BTS,并证明了该算法在一条分枝上回溯到网络相容状态的最坏时间复杂度是O（ned3）。实验结果表明：新的MAC_BTS算法在大多数问题的求解上较国际上流行的MAC3rm算法以及MAC_LC算法取得了10%~20%的加速,甚至在某些问题上达到50%,可见该算法在效率上更优。A new reasoning method based on successful backtracking is proposed,and a new corresponding constraint solving algorithm,named MAC_BTS,is developed.It is proved that the worst-case time complexity is O（ned3）on a branch.A large number of experimental results show that the proposed algorithm,MAC_BTS,is more efficient,which can obtain the accelerations about 10%to 20%（even 50% in some problems）compared with the popular existing constraint solving algorithms MAC3 rm and MAC_LC.

关 键 词：人工智能 约束满足问题 约束推理 成功回溯 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]