DPLL算法中的变量决策启发式策略

• 作者: 刘文秀 李千卉 江建国
• 来源期刊: 软件工程与应用
• 学科: 工学
• 关键词: DPLL算法 启发式策略 可满足性问题
• 年，卷（期）: 2016,（1）
• 页码范围: 47-55
• 页数: 9页
• 分类号: TP30

摘要

针对命题公式φ(CNF形式)的可满足性问题的求解效率问题,基于对DPLL完全算法的学习和在不同形式下对子句文字排序处理的研究,提出了一种新的求解SAT问题的算法。新算法根据子句长度对命题公式φ进行分组,并根据变量出现次数进行初始排序,然后考虑变量中正负文字出现的次数,并对次数高的进行赋值。算法实例表明:新算法能减少求解过程中规则使用次数,减少求解步骤,尽早剪除不满足解空间,从而有效提高求解效率。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	江建国	辽宁师范大学数学学院	17	88	4.0	9.0
2	李千卉	辽宁师范大学数学学院	2	0	0.0	0.0
3	刘文秀	辽宁师范大学数学学院	2	0	0.0	0.0