Research On Application Of Structural Entropy In Performance Analysis Of Message Propagation Algorithm

Constraint satisfaction problem(CSP)is an significant research field in artificial intelligence.Boolean satisfiability(SAT)problem a special kind of constraint satisfaction problem,which is widely used in computer science for application prospects.However,this problem is also NP-hard.At P! = NP condition,any exact solution algorithm can not get an precise solution to the issue in polynomial time currently.Therefore,the SAT problem has been widely concerned by scholars in mathematical logic and computer science.In the 1950 s,physicists proposed a factor graph-based message passing algorithm.This type of algorithm is very effective in solving SAT problems,but the performance of the algorithm depends on the structure of the factor graph.When the structure of the factor graph is more complicated,especially when there are loops in the factor graph,the message passing algorithm is not always effective,and often appears to be non-convergent.Therefore,convergence is the main indicator of the performance evaluation of message passing algorithm.As a dynamic measurement method,structural entropy can reflect the dynamic complexity of the network.Therefore,structural entropy makes up for the defect that information entropy cannot accurately reflect the complexity of the network structure,and can be used to measure important information such as node interaction complexity and internal structure complexity.The introduction of structural entropy can not only measure the complexity and uncertainty of the message passing algorithm in the factor graph and other important structural information,but also reflect the dynamic complexity of the random walk process in the algorithm.Structural entropy is a dynamic measurement method of structural complexity.The introduction of structural entropy can not only measure the complexity and uncertainty of the message passing algorithm on the factor graph and other important structural information,but also reflect the dynamic complexity of random walk process in the algorithm.In order to study the performance of the algorithm to solve the SAT problem more deeply,use structural entropy to analyze the structure information of factor graph of the random SAT instance.Based on the structure information,the convergence of the algorithm is further studied.Specifically,the main innovations are as follows Two points:(1)Propose the structure information of the proposition formula,and establish the multi-dimensional structure entropy measurement model of the proposition formula based on Warning Propagation(WP)algorithm.combine with the convergence of the WP Algorithm on the example,analyze the relationship between the convergence of the WP and the multi-dimensional structural entropy,and use the multi-dimensional structural entropy to measure the convergence of the WP,Give the convergence conditions of the WP based on multi-dimensional structural entropy.(2)In order to investigate the propagation process of the Survey Propagation(SP)Algorithm on the factor graph,the WPLPA algorithm is designed to divide the factor graph into communities,and establish the two-dimensional structure entropy measurement model of the proposition formula based on the WPLPA algorithm.The model is used to measure the factor graph in the SP algorithm.Analyze the structural complexity of the SP algorithm by using the two-dimensional structural entropy for analyze the convergence of the SP algorithm,and give the judgment conditions of the SP algorithm convergence.