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

作     者：王晓峰 许道云 姜久雷 唐延辉 无

作者机构：北方民族大学计算机科学系银川750021 贵州大学计算机科学系贵阳550025 

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

出 版 物：《中国科学：信息科学》 (Scientia Sinica(Informationis))

年 卷 期：2017年第47卷第12期

页      码：1646-1661页

摘      要：信息传播算法求解可满足问题时有良好的有效性,使得难解区域变窄.然而,信息传播算法不总有效,常表现为不收敛.对于这种现象,至今缺少系统的理论解释.调查传播(survey propagation,SP)算法是最为有效的信息传播算法,对SP算法的收敛性研究是设计其他信息传播算法的重要基础,并为信息传播算法的广泛应用提供理论依据.为了分析SP算法的收敛性,通过对消息更新方程取双曲正切,将消息取值从[0,1]扩展为(-∞,∞),利用压缩映射原理给出了SP算法收敛的一个充分条件.基于随机3-SAT实例,给出了SP算法收敛的一个概率条件.最后,选取了随机3-SAT实例进行数值实验模拟,验证了该条件的有效性.

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

学科分类：050302[050302] 05[文学] 0503[文学-新闻传播学类] 

核心收录：

D　O　I：10.1360/N112016-00248

馆 藏 号：203280242...