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

摘要

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