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

发布时间：2017-10-20 10:32

  本文关键词：警示传播算法收敛的充分条件

  更多相关文章： 警示传播算法 收敛性 可满足性问题 因子图

【摘要】：信息传播算法求解可满足问题时有惊人的效果,难解区域变窄.然而,因子图带有环的实例,信息传播算法不总有效,常表现为不收敛.对于这种现象,至今缺少系统的理论解释.警示传播(warning propagation,简称WP)算法是一种基础的信息传播算法,对WP算法的收敛性研究是其他信息传播算法收敛性研究的重要基础.在WP算法中,将警示信息的取值从{0,1}松弛为[0,1],利用压缩函数的性质,给出了WP算法收敛的一个充分条件.选取了两组不同规模的随机3-SAT实例进行实验模拟,结果表明:当子句与变元的比值?1.8时,该判定条件有效.
【作者单位】： 北方民族大学计算机科学系;贵州大学计算机科学系;
【关键词】： 警示传播算法 收敛性 可满足性问题 因子图
【基金】：国家自然科学基金(61462001,61262006,61402017) 宁夏自然科学基金(NZ14108) 北方民族大学基金(2014XYZ 03,2014XBZ04) “计算机应用技术”自治区重点学科项目~~
【分类号】：TP301.6
【正文快照】： 9825/4940.htm英文引用格式:Wang XF,Xu DY.Sufficient conditions for convergence of the warning propagation algorithm.Ruan Jian XueBao/Journal of Software,2016,27(12):3003?3013(in Chinese).http://www.jos.org.cn/1000-9825/4940.htmSufficient Conditions for Co

【相似文献】

中国期刊全文数据库 前10条

1 唐浩;;蚁群算法的研究与展望[J];牡丹江教育学院学报;2009年06期

2 邓小波;曹聪聪;龙伦海;康耀红;;蚁群算法搜索熵研究[J];海南大学学报(自然科学版);2007年04期

3 张康;顾幸生;;全局组搜索优化算法及其应用研究[J];青岛科技大学学报(自然科学版);2012年05期

4 李东晓;蒋珉;柴干;;蚁群算法优化及其在高速公路紧急救援中的应用[J];计算机技术与发展;2010年11期

5 _5文龙 ,黄，

本文编号：1066814