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

A Belief Propagation Algorithm for Constraint Satisfaction Problem Based on Backtracking

作　　者：林童 

机构地区：[1]上海理工大学,理学院,上海

出　　处：《应用数学进展》2023年第3期993-1002,共10页Advances in Applied Mathematics

摘　　要：针对一个典型的具有可变取值域的随机约束满足问题模型即RB模型,提出一种基于回溯的置信传播的算法。该算法在置信传播方程不收敛时,通过回溯对上一个变量进行重新赋值,从而将消去变量的过程继续进行下去。数值结果表明:这种基于回溯的置信传播算法能在可满足性相变区域找到问题的解,有效地提高了置信传播算法的求解效率。In this paper, we propose a belief propagation algorithm based on backtracking for a typical model of random constraint satisfaction problem with variable range, namely RB model. In this algorithm, when the belief propagation equation does not converge, it reassigns the previous variable by backtracking, so as to continue the process of variable elimination. The numerical results show that the backtracking belief propagation algorithm can find the solution of the problem in the satisfia-bility phase transition region, and effectively improve the efficiency of the belief propagation algo-rithm.

关 键 词：约束满足问题 RB模型 置信传播 回溯算法 

分 类 号：TP3[自动化与计算机技术—计算机科学与技术]