Affiliations: [a] School of Computer Science and Engineering, Northern University for Nationalities, Yinchuan, China
| [b] Key Laboratory of lmage and Graphics Intelligent Processing, State Ethnic Affairs Commission, Northern University for Nationalities, Yinchuan, China
Note: [1] This research was funded by the National Natural Science Foundation of China (62062001); Ningxia youth talent plan (2021).
Abstract: The survey propagation algorithm is the most effective information propagation algorithm for solving the 3-SAT problem. It can effectively solve the satisfiability problem when it converges. However, when the factor graph structure is complex, the algorithm often does not converge and the solution fails. In order to give a theoretical explanation to this phenomenon and to analyze the convergence of the survey propagation algorithm effectively, a connected treewidth model of the propositional formula was constructed by using the connected tree decomposition method, and the connected treewidth of the factor graph was calculated. The relationship between the connected treewidth and the convergence of the survey propagation algorithm is established, and the convergence judgment condition of the survey propagation algorithm based on the connected tree width is given. Through experimental analysis, the results show that the method is effective, which is of great significance for analyzing the convergence analysis of other information propagation algorithms.
