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

Convergence analysis of warning propagation algorithm based on structural entropy

作　　者：牛进 王晓峰[1] 林青文 Niu Jin;Wang Xiaofeng;Lin Qingwen(School of Computer Science&Engineering,North Minzu University,Yinchuan 750021,China)

机构地区：[1]北方民族大学计算机科学与工程学院,银川750021

出　　处：《计算机应用研究》2021年第3期760-763,776,共5页Application Research of Computers

基　　金：国家自然科学基金资助项目(61462001,61762019,61862051,61962002);北方民族大学重大专项资助项目(ZDZX201901);宁夏自然科学基金资助项目(NZ17111,2019AAC03120,2019AAC03119);北方民族大学校级科研一般项目(2019XYZJK05)。

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

关 键 词：可满足性问题 命题公式 结构熵 警示传播算法 收敛性 

分 类 号：TP393.04[自动化与计算机技术—计算机应用技术]