警示传播算法收敛的充分条件

王晓峰1许道云2

1.北方民族大学; 2.贵州大学;

摘要：

信息传播算法求解可满足问题时有惊人的效果,难解区域变窄.然而,因子图带有环的实例,信息传播算法不总有效,常表现为不收敛.对于这种现象,至今缺少系统的理论解释.警示传播(warning propagation,简称WP)算法是一种基础的信息传播算法,对WP算法的收敛性研究是其他信息传播算法收敛性研究的重要基础.在WP算法中,将警示信息的取值从{0,1}松弛为[0,1],利用压缩函数的性质,给出了WP算法收敛的一个充分条件,选取了两组不同规模的随机3-SAT实例进行实验模拟,结果表明:当子句与变元的比值α＜1.8时,该判定条件有效.

关键词：警示传播算法、收敛性、可满足性问题、因子图

所属期刊栏目：27

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金61462001,61262006,61402017;宁夏自然科学基金NZ14108;北方民族大学基2014XYZ03,2014XBZ04;“计算机应用技术”自治区重点学科项目;National Natural Science Foundation of China61462001,61262006,61402017;Natural Science Foundation of Ningxia Province of ChinaNZ14108;Natural Science Foundation of Beifang Unversity of Nationalities2014XYZ03,2014XBZ04;Key Subject Foundation of Computer application technology of Ningxia

在线出版日期：2017-01-06（万方平台首次上网日期，不代表论文的发表时间）

页数：共11页

页码：3003-3013