规则实例集上警示传播算法的收敛性

摘要：

信息传播算法求解随机3-SAT问题时非常有效,能使难解区域变窄.然而,对于因子图带有环的实例,信息传播算法并不总有效,常表现为不收敛.对于这种现象,至今缺少系统的理论解释.警示传播(Warning Propagation,WP)算法是一种基础的信息传播算法,对WP算法的收敛性研究是其它信息传播算法收敛性研究的重要基础.将一个3-SAT问题转换为具有规则结构的(3,4)-SAT问题,(3,4)-SAT问题是NP-完全的.基于(3,4)-SAT问题的规则结构性质,分析WP算法的收敛性.选取了3组不同规模的实例进行实验模拟,结果表明:在这种规则结构的可满足性实例集上,WP算法的收敛性有较大提高.

关键词：警示传播算法、收敛性、可满足性问题、规则结构

所属期刊栏目：42

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

资助基金：国家自然科学基金61363001,61262006,60863005,61462001;宁夏科学基金NXXT14009,NZ14108,NGY2012096;北方民族大学基金2014XYZ03,2014XYS17

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

页数：共6页

页码：279-284