基于警示传播与DPLL算法的启发式极性决策算法

• 作者: 王晓峰 秦永彬 许道云
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: 信息传递 警示传播算法 收敛性 DPLL算法
• 年，卷（期）: 2010,（12）
• 页码范围: 178-181,185
• 分类号: TP301
• 字数: 5611字
• 语种: 中文
• DOI: 10.3969/j.issn.1002-137X.2010.12.040

摘要

警示传播(WP)算法是信息传播算法的重要基础,WP算法的本质是因子图上警示信息的迭代过程,在算法收敛时得到一组稳定的警示信息,并利用局部腔域得到公式变元的部分赋值.分析了警示传播算法的基本原理,给出了算法的改进.RB实例集上的实验证明,改进后的算法比原算法具有迭代次数和运行时间,提高了收敛速度.然而,在RB模型产生的大部分实例集上,警示传播算法不收敛,因而不能有效求解公式.警示传播算法与DPLL算法的组合使用使回溯计算次数大大降低,从而有效地弥补了WP算法的不足.通过在RB实例集上的测试实验表明,该方法是有效的.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	许道云	贵州大学计算机科学与信息学院	125	460	12.0	16.0
2	王晓峰	贵州大学计算机科学与信息学院	26	122	6.0	9.0
3	秦永彬	贵州大学计算机科学与信息学院	63	213	8.0	10.0