基于边际概率分布重新进行单变量选取的置信传播算法求解约束满足问题

Belief Propagation Algorithm for Solving Constraint Satisfaction Problem Based on Marginal Probability Distribution with Re-Selection of Univariate

摘要: 针对RB模型这一类具有增长取值域的随机约束满足问题，提出一种基于边际概率分布重新进行单变量选取的置信传播算法。该算法在置信传播方程不收敛时，通过边际概率分布顺序由大到小找到下一个变量进行重新赋值，从而消去变量的过程。实验结果表明：这种重新挑选变量进行赋值的置信传播算法能在可满足相变区域找到问题的解，有效地提高了置信传播地求解效率。

Abstract: Aiming at the RB model which has a growing value range of stochastic constraint satisfaction problem, a belief propagation algorithm based on marginal probability distribution is proposed. When the belief propagation equation does not converge, the algorithm finds the next variable to be reassigned by the order of marginal probability distribution from large to small, so as to eliminate the process of variables. Experimental results show that the belief propagation algorithm based on reselecting variables for assignment can find the solution of the problem in the region that can satisfy the phase change, and effectively improves the efficiency of belief propagation.