调查传播算法收敛的一个充分条件  

Sufficient conditions for convergence of the survey propagation algorithm

作　　者：王晓峰[1,2] 许道云[2] 姜久雷[1] 唐延辉 

机构地区：[1]北方民族大学计算机科学系,银川750021 [2]贵州大学计算机科学系,贵阳550025

出　　处：《中国科学：信息科学》2017年第12期1646-1661,共16页Scientia Sinica(Informationis)

基　　金：国家自然科学基金(批准号:61462001;61650206;61563001;61402017);计算机应用技术自治区重点学科建设基金资助项目

摘　　要：信息传播算法求解可满足问题时有良好的有效性,使得难解区域变窄.然而,信息传播算法不总有效,常表现为不收敛.对于这种现象,至今缺少系统的理论解释.调查传播(survey propagation,SP)算法是最为有效的信息传播算法,对SP算法的收敛性研究是设计其他信息传播算法的重要基础,并为信息传播算法的广泛应用提供理论依据.为了分析SP算法的收敛性,通过对消息更新方程取双曲正切,将消息取值从[0,1]扩展为(-∞,∞),利用压缩映射原理给出了SP算法收敛的一个充分条件.基于随机3-SAT实例,给出了SP算法收敛的一个概率条件.最后,选取了随机3-SAT实例进行数值实验模拟,验证了该条件的有效性.Message propagation algorithms are very effective at finding satisfying assignments for SAT instances,and hard regions of a random SAT have become narrower. However, message propagation algorithms do not always converge for some random SAT instances. Unfortunately, a rigorous theoretical proof of this phenomenon is still lacking. The survey propagation（SP） algorithm is very effective at solving SAT instances, and a theoretical analysis of SP is very important in designing other message passing algorithms. Through this study, we derived the sufficient conditions for convergence of SP with extending message [0, 1] to message（-∞, ∞）. Finally,the experiment results show that the conditions for the convergence of SP are very effective in random 3-SAT instances.

关 键 词：调查传播算法 可满足性问题 收敛性 信息传播算法 因子图 

分 类 号：G206[文化科学—传播学]