基于K维结构熵的调查传播算法收敛性分析

来源：计算机应用研究杂志2022年第5期北京时间：

作者：梁晨,王晓峰,刘子琳,芦磊,牛鹏飞,

单位：北方民族大学a.计算机科学与工程学院;b.图像图形智能处理国家民委重点实验室,银川750021；

摘要：信息传播算法在可满足性（SAT）问题上性能表现优越，其收敛性却依赖于因子图的结构复杂程度，至今缺少系统的理论解释。调查传播算法（SP）是解决SAT问题效果最好的信息传播算法。为有效分析SP算法的收敛性，借助因子图转换技术和鲁汶算法划分因子图社区，基于K维结构熵理论，提出了SAT实例的K维结构熵度量模型，得出了随机SAT实例的K维结构熵。分析了SP算法收敛性与K维结构熵之间的关系，给出了SP算法收敛性的K维结构熵阈值。实验证明该方法有效。

关键词：可满足性问题,K维结构熵,调查传播算法,收敛性,

基金资助：国家自然科学基金资助项目(62062001,61762019,61862051,61962002)；北方民族大学重大专项资助项目(ZDZX201901)；宁夏自然科学基金资助项目(2020AAC03214,2020AAC03219,2019AAC03120,2019AAC03119)；；