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

作者：张学才; 赵春艳^*

来源：计算机应用研究, 2022, 39(05): 1427-1431.

DOI：10.19734/j.issn.1001-3695.2021.09.0433

• 约束满足问题
• 动态度
• 回溯算法
• 维持弧相容

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

• 单位
  上海理工大学