Page 136 - 《软件学报》2021年第5期

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
Journal of Software,2021,32(5):1360−1372 [doi: 10.13328/j.cnki.jos.005844] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563

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

3
1
1,2
2
1
王晓峰 , 许道云 , 杨德仁 , 姜久雷 , 李 强 , 刘欣欣 1
1
(北方民族大学 计算机科学与工程学院,宁夏 银川 750021)
2
(贵州大学 计算机科学与技术学院,贵州 贵阳 550025)
3 (宁夏医科大学 理学院,宁夏 银川 750004)
通讯作者: 杨德仁, E-mail: deren.yang@nxmu.edu.cn

摘 要: 信念传播算法是基于因子图模型的消息传递算法,通过图中的边,将消息从一个结点传递给另一个结点,
以高概率地确定部分变量的取值,这种方法被实验证明在求解可满足性问题时非常有效.然而,目前还未对其有效性
从理论角度给予解释.通过对信念传播算法的收敛性分析,试图从理论上解释算法的有效性.在信息传播算法的信息
迭代方程中,参数的取值范围为(0,1),将该取值范围扩展到整个实数空间,即(−∞,+∞).利用压缩函数的数学原理,得到
了信息迭代方程收敛的判定条件.选取随机可满足性问题实例进行实验模拟,验证了结论的正确性.
关键词: 信念传播算法;收敛性;可满足性问题;因子图
中图法分类号: TP301

中文引用格式: 王晓峰,许道云,杨德仁,姜久雷,李强,刘欣欣.可满足性问题中信念传播算法的收敛性分析.软件学报,2021,
32(5):1360−1372. http://www.jos.org.cn/1000-9825/5844.htm
英文引用格式: Wang XF, Xu DY, Yang DR, Jiang JL, Li Q, Liu XX. Convergence analysis of belief propagation algorithm for
satisfiability problem. Ruan Jian Xue Bao/Journal of Software, 2021,32(5):1360−1372 (in Chinese). http://www.jos.org.cn/1000-
9825/5844.htm
Convergence Analysis of Belief Propagation Algorithm for Satisfiability Problem

1
2
1,2
3
1
WANG Xiao-Feng , XU Dao-Yun , YANG De-Ren , JIANG Jiu-Lei , LI Qiang , LIU Xin-Xin 1
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

∗ 基金项目: 国家自然科学基金(62062001, 61762019, 61762002, 61862051, 61962002); 宁夏自然科学基金(2020AAC03214,
NZ17111, 2019AAC03120, 2019AAC03119, 2020AAC03219); 北方民族大学重大专项基金(ZDZX201901); 北方民族大学校级一般
科学基金(2019XYZJK05)
Foundation item: National Natural Science Foundation of China (62062001, 61762019, 61762002, 61862051, 61962002); Natural
Science Foundation of Ningxia (2020AAC03214, NZ17111, 2019AAC03120, 2019AAC03119, 2020AAC03219); Major Scientific
Research Projects of North Minzu University (ZDZX201901); Scientific Research Projects of North Minzu University (2019XYZJK05)
收稿时间: 2018-06-22; 修改时间: 2018-11-22; 采用时间: 2019-03-25