微信服务号

微信订阅号

2025-4-24- 13
Home > Archive>Volume 32, Issue 5, 2021 >1360-1372. DOI:10.13328/j.cnki.jos.005844
PDF HTML XML Export Cite reminder
Convergence Analysis of Belief Propagation Algorithm for Satisfiability Problem
Author:
Affiliation:

Clc Number:

TP301

Fund Project:

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)

  • Article
    • | |
  • Metrics
    • |
  • Reference
    • |
  • Related
    • |
  • Cited by
    • | |
  • Comments
    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.

    Reference
    Related
    Cited by
Get Citation

王晓峰,许道云,杨德仁,姜久雷,李强,刘欣欣.可满足性问题中信念传播算法的收敛性分析.软件学报,2021,32(5):1360-1372

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:June 22,2018
  • Revised:November 22,2018
  • Online: May 07,2021
  • Published: May 06,2021
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063