基于动态度的回溯算法求解大值域约束满足问题  

Dynamic degree based backtracking algorithm to solve constraint satisfaction problems with large domains

作　　者：张学才 赵春艳 Zhang Xuecai;Zhao Chunyan(College of Science,University of Shanghai for Science&Technology,Shanghai 200093,China)

机构地区：[1]上海理工大学理学院,上海200093

出　　处：《计算机应用研究》2022年第5期1427-1431,共5页Application Research of Computers

基　　金：国家自然科学基金资助项目(11301339);国家自然科学基金国际(地区)合作与交流项目(11491240108)。

摘　　要：针对一个具有精确可满足性相变现象的大值域随机约束满足问题,提出了两种启发式动态回溯算法,即基于动态度的ddeg-MAC(dynamic degree-maintaining arc consistency)回溯算法和基于值域与动态度比值的dom/ddeg-MAC(dom/dynamic degree-maintaining arc consistency)回溯算法。这两种算法分别基于ddeg和dom/ddeg挑选变量,利用维持弧相容(MAC)技术为挑选的变量进行赋值。当赋值无法进行时,再执行动态回溯修正变量的赋值。数值实验结果表明:在控制参数非常接近理论相变点时,算法仍然能够有效地找到问题的解。与经典回溯算法相比,这两种启发式动态回溯算法具有显著的优越性。This paper proposed two heuristic dynamic backtracking algorithms which called ddeg-MAC backtracking algorithm based on dynamic degree and dom/ddeg-MAC backtracking algorithm based on dom/ddeg,respectively.The two algorithms chose variable according to the ddeg of the variable and the dom/ddeg of the variable,respectively.Both of the algorithms used maintaining arc consistency technique to assign the selected variables.When the assignment of the variabled violates the constraint,it performed dynamic backtracking to correct the value of the nearest variable.Numerical results show that the algorithms can find the solution of the problem effectively when the control parameter is very close to the theoretical phase transition point.Compared to the classical backtracking algorithm,the two heuristic dynamic backtracking algorithms have significant advantages.

关 键 词：约束满足问题 动态度 回溯算法 维持弧相容 

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