可满足性问题中信念传播算法的收敛性分析  

Convergence Analysis of Belief Propagation Algorithm for Satisfiability Problem

作　　者：王晓峰[1,2] 许道云[2] 杨德仁[3] 姜久雷[1] 李强[1] 刘欣欣 WANG Xiao-Feng;XU Dao-Yun;YANG De-Ren;JIANG Jiu-Lei;LI Qiang;LIU Xin-Xin(School of Computer Science and Engineering,North Minzu University,Yinchuan 750021,China;School of Computer Science and Technology,Guizhou University,Guiyang 550025,China;School of Science,Ningxia Medical University,Yinchuan 750004,China)

机构地区：[1]北方民族大学计算机科学与工程学院,宁夏银川750021 [2]贵州大学计算机科学与技术学院,贵州贵阳550025 [3]宁夏医科大学理学院,宁夏银川750004

出　　处：《软件学报》2021年第5期1360-1372,共13页Journal of Software

基　　金：国家自然科学基金(62062001,61762019,61762002,61862051,61962002);宁夏自然科学基金(2020AAC03214,NZ17111,2019AAC03120,2019AAC03119,2020AAC03219);北方民族大学重大专项基金(ZDZX201901);北方民族大学校级一般科学基金(2019XYZJK05)。

摘　　要：信念传播算法是基于因子图模型的消息传递算法,通过图中的边,将消息从一个结点传递给另一个结点,以高概率地确定部分变量的取值,这种方法被实验证明在求解可满足性问题时非常有效.然而,目前还未对其有效性从理论角度给予解释.通过对信念传播算法的收敛性分析,试图从理论上解释算法的有效性.在信息传播算法的信息迭代方程中,参数的取值范围为(0,1),将该取值范围扩展到整个实数空间,即(−∞,+∞).利用压缩函数的数学原理,得到了信息迭代方程收敛的判定条件.选取随机可满足性问题实例进行实验模拟,验证了结论的正确性.Belief propagation(BP)algorithm is a message passing algorithm based on a factor graph,and it passes messages from one node to another through edges in the graph to determine the value of some variables with high probability.This method is experimentally proven to be very effective when solving the satisfiability(SAT)problem.However,there is no explanation for its effectiveness from a theoretical point of view at present.Through the analysis of convergence of the BP algorithm,the effectiveness of the algorithm is explained theoretically.In this study,the sufficient conditions are also derived for convergence of the BP for satisfiability problem,and extending message(0,1)to message(−∞,+∞).Lastly,experimental results show that the conditions for convergence of BP are very effective in random SAT instances,and it proves the correctness of the conclusion.

关 键 词：信念传播算法 收敛性 可满足性问题 因子图 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]