| 本文已被：浏览 1870次 下载 4563次 |
码上扫一扫！ |
|
|
| 可满足性问题中信念传播算法的收敛性分析 |
|
王晓峰1,2, 许道云2, 杨德仁3, 姜久雷1, 李强1, 刘欣欣1
|
|
1.北方民族大学 计算机科学与工程学院, 宁夏 银川 750021;2.贵州大学计算机科学与技术学院, 贵州 贵阳 550025;3.宁夏医科大学 理学院, 宁夏 银川 750004
|
|
| 摘要: |
| 信念传播算法是基于因子图模型的消息传递算法，通过图中的边，将消息从一个结点传递给另一个结点，以高概率地确定部分变量的取值，这种方法被实验证明在求解可满足性问题时非常有效.然而，目前还未对其有效性从理论角度给予解释.通过对信念传播算法的收敛性分析，试图从理论上解释算法的有效性.在信息传播算法的信息迭代方程中，参数的取值范围为（0，1），将该取值范围扩展到整个实数空间，即（-∞，+∞）.利用压缩函数的数学原理，得到了信息迭代方程收敛的判定条件.选取随机可满足性问题实例进行实验模拟，验证了结论的正确性. |
| 关键词: 信念传播算法 收敛性 可满足性问题 因子图 |
| DOI：10.13328/j.cnki.jos.005844 |
| 分类号:TP301 |
| 基金项目:国家自然科学基金（62062001，61762019，61762002，61862051，61962002）；宁夏自然科学基金（2020AAC03214，NZ17111，2019AAC03120，2019AAC03119，2020AAC03219）；北方民族大学重大专项基金（ZDZX201901）；北方民族大学校级一般科学基金（2019XYZJK05） |
|
| Convergence Analysis of Belief Propagation Algorithm for Satisfiability Problem |
|
WANG Xiao-Feng1,2, XU Dao-Yun2, YANG De-Ren3, JIANG Jiu-Lei1, LI Qiang1, LIU Xin-Xin1
|
|
1.School of Computer Science and Engineering, North Minzu University, Yinchuan 750021, China;2.School of Computer Science and Technology, Guizhou University, Guiyang 550025, China;3.School of Science, Ningxia Medical University, Yinchuan 750004, China
|
| Abstract: |
| 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. |
| Key words: belief propagation (BP) algorithm convergence satisfiability problem factor graph |
