WP可解公式上警示传播算法收敛的有效条件

• 作者: 崔立 牛进 王晓峰
• 来源期刊: 计算机应用研究
• 关键词: 警示传播算法 骨干集 后门集 WP-可解公式 实例产生模型
• 年，卷（期）: 2020,（5）
• 所属期刊栏目: 算法研究探讨
• 页码范围: 1406-1410
• 页数: 5页
• 分类号: TP301.6
• 语种: 中文
• DOI: 10.19734/j.issn.1001-3695.2018.11.0791

摘要

通过对警示传播(warning propagation,WP)算法的数学原理分析,高概率确定的部分变元与公式的骨干集和后门集有密切关系.针对WP算法收敛性的研究,基于骨干集和后门集定义WP-可解公式,利用在G(n,3,m)模型和植入指派模型下证明WP算法的收敛性,给出算法收敛的充要条件.最后,通过在植入指派的公式产生模型上进行数值实验验证,结果表明:如果一个可满足性公式WP-可解公式,当且仅当WP算法高概率收敛.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王晓峰	北方民族大学计算机科学与工程学院	14	23	4.0	4.0
2	崔立	北方民族大学计算机科学与工程学院	1	0	0.0	0.0
3	牛进	北方民族大学计算机科学与工程学院	1	0	0.0	0.0