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

来源：计算机应用研究杂志2022年第5期北京时间：

作者：张学才,赵春艳,

单位：上海理工大学理学院,上海200093；

摘要：针对一个具有精确可满足性相变现象的大值域随机约束满足问题，提出了两种启发式动态回溯算法，即基于动态度的ddeg-MAC（dynamic degree-maintaining arc consistency）回溯算法和基于值域与动态度比值的dom/ddeg-MAC（dom/dynamic degree-maintaining arc consistency）回溯算法。这两种算法分别基于ddeg和dom/ddeg挑选变量，利用维持弧相容（MAC）技术为挑选的变量进行赋值。当赋值无法进行时，再执行动态回溯修正变量的赋值。数值实验结果表明：在控制参数非常接近理论相变点时，算法仍然能够有效地找到问题的解。与经典回溯算法相比，这两种启发式动态回溯算法具有显著的优越性。

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

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