-
题名基于K维结构熵的调查传播算法收敛性分析
被引量：2
- 1
-
-
作者
梁晨
王晓峰
刘子琳
芦磊
牛鹏飞
-
机构
北方民族大学计算机科学与工程学院
北方民族大学图像图形智能处理国家民委重点实验室
-
出处
《计算机应用研究》
CSCD
北大核心
2022年第5期1432-1436,共5页
-
基金
国家自然科学基金资助项目(62062001,61762019,61862051,61962002)
北方民族大学重大专项资助项目(ZDZX201901)
宁夏自然科学基金资助项目(2020AAC03214,2020AAC03219,2019AAC03120,2019AAC03119)。
-
文摘
信息传播算法在可满足性(SAT)问题上性能表现优越,其收敛性却依赖于因子图的结构复杂程度,至今缺少系统的理论解释。调查传播算法(SP)是解决SAT问题效果最好的信息传播算法。为有效分析SP算法的收敛性,借助因子图转换技术和鲁汶算法划分因子图社区,基于K维结构熵理论,提出了SAT实例的K维结构熵度量模型,得出了随机SAT实例的K维结构熵。分析了SP算法收敛性与K维结构熵之间的关系,给出了SP算法收敛性的K维结构熵阈值。实验证明该方法有效。
-
关键词
可满足性问题
K维结构熵
调查传播算法
收敛性
-
Keywords
satisfiability problem
K-dimensional structural entropy
survey propagation algorithm
convergence
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-
