启发式回溯算法求解约束满足问题

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

作者：范如梦,赵春艳,李飞龙,

单位：1.上海理工大学理学院,上海200093；2.无锡商业职业技术学院基础教学部,江苏无锡214153；

摘要：针对一个典型的具有可变取值域的随机约束满足问题，提出了利用度启发式策略和最少约束值启发式策略来选择变量进行赋值的不完备回溯算法。该算法首先通过度启发式来确定待赋值变量的顺序，然后利用最少约束值启发式对选择的变量进行赋值，最后在有限时间内通过回溯得到变量的一组取值。用此算法对由RB模型生成的随机实例进行求解，实验结果表明，与经典的回溯算法相比，该算法具有显著的优越性。在控制参数（即约束紧度）进入相变区域时，该算法能在较短的时间内有效地找到实例的解。

关键词：约束满足问题,RB模型,回溯算法,度启发式,最少约束值启发式,

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