Performance Analysis Study Of Message Propagation Algorithms Based On Tree Decomposition

As a class of combinatorial optimisation problems,the goal of SAT is to determine whether there is a set of assignments such that all clauses of the Conjunctive Normal Form(CNF)are satisfied,i.e.the propositional formula is true.Many real-world application problems can be transformed into SAT problems for solution.As a result,SAT problems have been receiving a lot of attention from scholars.Message propagation algorithms designed by physicists based on the cavity-domain approach are able to solve SAT problems effectively,outperforming completeness algorithms,and are particularly effective in solving difficult regions.However,as the problem size becomes complex,corresponding to the increase of loops in the factor graph,message propagates in the process of iteration,loops appear and the algorithm gradually fails.Therefore,convergence has an important influence on the effective solution of message propagation algorithms.Treewidth is used as a metric parameter for graph structure features,and many hard problems can be solved efficiently under restricted treewidth conditions.Treewidth measures are introduced to factor graph structure features to explore the link between the solution performance of information propagation algorithms and treewidth.In this paper,a factor graph structure treewidth volume model for three information propagation algorithms for solving satisfiability problems is designed,and convergence treewidth thresholds for the three algorithms are given,specifically,the following studies.(1)The tree decomposition method is used to construct a treewidth volume model of the factor graph corresponding to the propositional formulae and to calculate the treewidth that can satisfy the random instances.The connection between treewidth and convergence of the alert propagation algorithm is established,the variation between treewidth and convergence rate of the warning propagation algorithm under different variant size instances is analysed,and the conditions for determining the convergence of the warning propagation algorithm based on treewidth are given.(2)A genetic algorithm-based genetic factor graph tree decomposition algorithm(GAFTW)is proposed to perform tree decomposition of factor graphs using the GAFTW algorithm according to the iterative characteristics of the belief propagation algorithm on factor graphs.Finding a better elimination point sequence in the population iteration of the genetic algorithm to get a smaller tree width.The relationship between treewidth and convergence of belief propagation algorithm is modeled by using the treewidth parameter to measure the structural characteristics of the factor graph,and the convergence of belief propagation algorithm is systematically analyzed,and the conditions for determining the convergence of BP algorithm based on tree decomposition are given.(3)Connected tree decomposition is a more accurate measure of loop size in graphs compared to tree decomposition,and the survey propagation algorithm is the most effective among the three message propagation algorithms for solving complex factor graph instances with loops.Therefore,a connected tree width measure model for propositional formulas is constructed using the connected tree decomposition method to calculate the connected tree width of factor graphs.The relationship between the connected treewidth and the convergence of the survey propagation algorithm is established,the relationship between the growth of the connected treewidth and the complexity of the factor graph structure is analysed,and the conditions for determining the convergence of the survey propagation algorithm based on the connected treewidth are given.