求解可满足性问题的信息传播算法研究综述

信息传播算法来自统计物理，被广泛应用于人工智能各个领域，特别是求解组合优化问题时，具有良好的有效性。通过对信息传播算法的相关文献进行分析，综述了信息传播算法以及其相关应用的发展史，根据信息传播算法的发展，介绍了求解可满足性问题的信息传播算法相关概念，主要涉及到警示传播算法、置信传播算法和调查传播算法，描述了三种算法发展中出现的收敛性、有效性研究，分别综述了各个算法在相关领域的应用情况，并总结了信息传播算法的研究路径和应用方向。

Overview of message propagation algorithm for satisfiability problems

Message propagation algorithms from statistical physics are widely used in various fields of artificial intelligence, especially in solving combinatorial optimization problems. According to the related literatures of message propagation algorithm, this paper summarized the history of message propagation algorithm and its related application. According to the deve-lopment of message propagation algorithm, it introduced the concepts of information propagation algorithm for solving the satisfiability problem, which mainly involved the warning propagation algorithm, the belief propagation algorithm and the survey propagation algorithm. This paper described the convergence and effectiveness research of the three kind of algorithms, summarized the application of each algorithm in related fields, and summarized the research path and application direction of message propagation algorithm.