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

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

Convergence analysis of survey propagation algorithm based on K-dimensional structure entropy

Survey propagation(SP) algorithm is the most effective information propagation algorithm. However, the algorithm does not often converge when it encounters factor graphs of complex structures. In order to explain this phenomenon theoretically, based on the theory of K-dimension structure entropy, and with the help of factor graph transformation technology and Leuven algorithm to divide factor graph community, this paper proposed the K-dimension structure entropy measurement model of propositional formula, and obtained the K-dimension structure entropy of random satisfiability instance. This paper analyzed the relation between the convergence of SP algorithm and K-dimension structure entropy, and gave the threshold of K-dimension structure entropy for SP algorithm convergence. The experimental results show that the method is effective.