基于结构熵的警示传播算法收敛性分析

收敛性是评价信息传播算法性能的重要指标,信息传播算法求解可满足性问题时,命题公式的结构特征影响算法的收敛性,具有复杂结构的命题公式,信息传播算法不总收敛。为了系统地对此现象给予理论解释,借助于结构熵的方法和技术,提出命题公式的结构熵模型及其度量方法,计算随机可满足性实例的结构熵。警示传播算法(WP)作为信息传播算法的基本模型,分析WP算法的收敛性对于研究其他信息传播算法的收敛性具有重要意义,分析了WP算法收敛性与结构熵之间的关系,给出WP算法收敛的判定条件。通过实验分析,该方法有效可行。

Convergence analysis of warning propagation algorithm based on structural entropy

Convergence is an important index for evaluating the performance of information propagation algorithms.When the information propagation algorithm solves the satisfiability problem,the structural characteristics of the proposition formula affect the convergence of the algorithm,propositional formulas with complex structures do not always converge on information propagation algorithms.For this phenomenon,there are few systematic theoretical explanations.As the basic model of the information propagation algorithm,the warning propagation(WP)algorithm analyzed the convergence of the WP algorithm was of great significance to study the convergence of other information propagation algorithms.With the help of structural entropy methods and techniques,this paper proposed a structural entropy model of propositional formula and its measurement method.This paper calculated the structural entropy of a random satisfiability instance,analyzed the relationship between the convergence of the WP algorithm and the structural entropy,and gave the judgment condition of convergence of WP algorithm.Through experimental analysis,this method is effective and feasible.