一种基于置信传播的算法求解随机约束满足问题

A Belief Propagation Based Algorithm for Solving Stochastic Constraint Satisfaction Problem

摘要: 为了求解具有增长域的随机约束满足问题(CSP)，提出一种基于置信传播的算法即NBP* (new-selected belief propagation*, NBP*)。在置信传播算法中，当BP方程不收敛时，算法就会终止。然而算法在经过多次迭代之后，虽然约束发送给变量的信息没有达到收敛条件，但是仍有部分信息是准确的，所以当算法的BP方程不收敛时，提出利用最后一次迭代得到的约束发送给变量的信息来计算变量的边际概率，当赋值不满足约束时，根据边际概率确定的变量顺序挑选下一个变量进行赋值，得到NBP*算法。数值实验表明：这种算法可以在可满足性相变区域找到解，并且有效提高了置信传播算法的求解效率。

Abstract: In order to solve the stochastic constraint satisfaction problem (CSP) with a growing domain, a belief propagation based algorithm called NBP* (new selected belief propagation*, NBP*) is proposed. In the belief propagation algorithm, when the BP equation does not converge, the algorithm will terminate. However, after multiple iterations, although the information sent by the constraint to the variable did not meet the convergence condition, some information was still accurate. Therefore, when the BP equation of the algorithm does not converge, it is proposed to use the information sent by the constraint to the variable from the last iteration to calculate the marginal probability of the variable. When the assignment does not meet the constraint, the next variable is selected according to the variable order determined by the marginal probability for assignment, resulting in the NBP* algorithm. Numerical experiments have shown that this algorithm can find solutions in the satisfiable phase transition region and effectively improve the efficiency of the confidence propagation algorithm.