一种基于变量熵求解约束满足问题的置信传播算法

在置信传播(belief propagation,BP)算法中,提出一种基于变量熵来挑选变量从而固定变量赋值的策略,用于求解一类具有增长定义域的随机约束满足问题.RB模型是一个具有增长定义域的随机约束满足问题的典型代表,已经严格证明它不仅存在精确的可满足性相变现象,而且可以生成难解实例.在RB模型上选取两组不同的参数进行数值实验.结果表明:在接近可满足性相变点时,BP引导的消去算法仍然可以非常有效地找到随机实例的解;不断增加问题的规模,算法的运行时间呈指数级增长;并且当控制参数(约束紧度)增加时,变量的平均自由度逐渐降低.

A belief-propagation algorithm based on variable entropy for constraint satisfaction problems

Belief propagation(BP) is a powerful technique that has been applied to solve constraint satisfaction problems(CSPs).In this paper,for solving random CSPs with growing domains,we propose a new strategy based on the variable entropy to fix variables in the procedure of BP decimation.It has been proved that model RB,a representative random CSP with growing domains,exhibits an exact satisfiability phase transition phenomenon,and all instances of model RB are hard at the threshold.We perform the algorithm on the instances of model RB with two different groups of parameters.Numerical results show that the algorithm guided by BP can find solutions efficiently for instances in the regime that is close to the threshold.The running time of the algorithm grows exponentially with the problem size.Besides,the average freedom of the variables decreases as the control parameter(constraint tightness) increases.