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

Overview of message propagation algorithm for satisfiability problems

作　　者：谢志新 王晓峰[1,2] 曹泽轩 于卓 莫淳惠 吴宇翔 Xie Zhixin;Wang Xiaofeng;Cao Zexuan;Yu Zhuo;Mo Chunhui;Wu Yuxiang(School of Computer Science&Engineering,North Minzu University,Yinchuan 750021,China;Key Laboratory of Image&Graphics Intelligent Processing of State Ethnic Affairs Commission,North Minzu University,Yinchuan 750021,China)

机构地区：[1]北方民族大学计算机科学与工程学院,银川750021 [2]北方民族大学图形图像智能处理国家民委重点实验室,银川750021

出　　处：《计算机应用研究》2022年第7期1933-1940,共8页Application Research of Computers

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

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

关 键 词：信息传播算法 组合优化 可满足性问题 警示传播 置信传播 调查传播 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]