计算机应用研究2021，Issue(3) ：760-763,776.DOI:10.19734/j.issn.1001-3695.2020.03.0053

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

Convergence analysis of warning propagation algorithm based on structural entropy

牛进 王晓峰 林青文
计算机应用研究2021，Issue(3) ：760-763,776.DOI:10.19734/j.issn.1001-3695.2020.03.0053
✕
  • 国家科技期刊平台
  • NETL
  • NSTL
  • 维普
  • 万方数据

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

Convergence analysis of warning propagation algorithm based on structural entropy

牛进 1王晓峰 1林青文1
扫码查看

作者信息

  • 1. 北方民族大学 计算机科学与工程学院,银川750021
  • 折叠

摘要

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

关键词

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

引用本文复制引用

基金项目

国家自然科学基金资助项目(61462001)

国家自然科学基金资助项目(61762019)

国家自然科学基金资助项目(61862051)

国家自然科学基金资助项目(61962002)

北方民族大学重大专项资助项目(ZDZX201901)

宁夏自然科学基金资助项目(NZ17111)

宁夏自然科学基金资助项目(2019AAC03120)

宁夏自然科学基金资助项目(2019AAC03119)

北方民族大学校级科研一般项目(2019XYZJK05)

出版年

2021
计算机应用研究
四川省电子计算机应用研究中心

计算机应用研究

CSTPCDCSCD北大核心
影响因子：0.93
ISSN：1001-3695
被引量2
参考文献量3
段落导航相关论文