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

摘要：

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

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

分类号：TP393.04(计算技术、计算机技术)

资助基金：国家自然科学基金资助项目;北方民族大学重大专项资助项目;宁夏自然科学基金资助项目;北方民族大学校级科研一般项目

在线出版日期：2021-03-18（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：760-763,776