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

Heuristic backtracking algorithm to solve constraint satisfaction problems

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

This paper proposed an incomplete backtracking algorithm to solve a typical random constraint satisfaction problem with growing domains,which used degree heuristic strategy and minimum constraint value heuristic strategy to assign the variables.The algorithm first determined the order of the variables to be assigned by degree heuristics,then used minimum constraint value heuristic to assign the selected variables,and finally obtained a set of values of the variables by backtracking in a limited time.The experimental results show that the algorithm is superior to the classical backtracking algorithm.When the control parameter(constraint tightness)enters the phase transition region,the algorithm can effectively find the solution of the instances in a short time.