论文部分内容阅读
在置信传播(belief propagation,BP)算法中,提出一种基于变量熵来挑选变量从而固定变量赋值的策略,用于求解一类具有增长定义域的随机约束满足问题.RB模型是一个具有增长定义域的随机约束满足问题的典型代表,已经严格证明它不仅存在精确的可满足性相变现象,而且可以生成难解实例.在RB模型上选取两组不同的参数进行数值实验.结果表明:在接近可满足性相变点时,BP引导的消去算法仍然可以非常有效地找到随机实例的解;不断增加问题的规模,算法的运行时间呈指数级增长;并且当控制参数(约束紧度)增加时,变量的平均自由度逐渐降低.
In belief propagation (BP) algorithm, a strategy of variable assignment based on variable entropy to fix variable assignment is proposed to solve a class of stochastic constraint satisfaction problem with growth domain.RB model is a new algorithm with growth definition It has been strictly proved that it not only has the exact satisfiability phase transition phenomenon but also can generate the inexact instances.Selecting two different sets of parameters on the RB model for the numerical experiments.The results show that in the BP-directed elimination algorithm can still find the solution of stochastic instances very effectively when it approaches the satisfiability phase transition point; increasing the scale of the problem, the algorithm runs exponentially; and as the control parameter (constraint compactness) increases , The average degree of freedom of variables gradually decreases.