摘要
信息传播算法求解可满足问题时有良好的有效性,使得难解区域变窄.然而,信息传播算法不总有效,常表现为不收敛.对于这种现象,至今缺少系统的理论解释.调查传播(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.
出处
《中国科学：信息科学》
CSCD
北大核心
2017年第12期1646-1661,共16页
Scientia Sinica(Informationis)
基金
国家自然科学基金(批准号:61462001
61650206
61563001
61402017)
计算机应用技术自治区重点学科建设基金资助项目
关键词
调查传播算法
可满足性问题
收敛性
信息传播算法
因子图
survey propagation algorithms, satisfiability problems, convergence, message passing algorithms, factor graph
