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

• 作者: 丁红胜 李强 王晓峰
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: 警示传播算法 收敛性 可满足性问题 规则结构
• 年，卷（期）: 2015,（1）
• 所属期刊栏目: 人工智能
• 页码范围: 279-284
• 页数: 6页
• 分类号: TP301
• 字数: 7790字
• 语种: 中文
• DOI: 10.11896/j.issn.1002-137X.2015.1.062

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	丁红胜	北方民族大学计算机科学系	16	71	5.0	7.0
2	李强	北方民族大学计算机科学系	25	46	4.0	5.0
3	王晓峰	北方民族大学计算机科学系	14	23	4.0	4.0