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

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

基于随机方法和优化的DPLL算法的测试用例自动生成技术研究

提出一种基于随机方法和优化的DPLL算法的测试用例自动生成技术,并以基于FPGA的核电仪控系统为对象进行了验证。该方法能验证HDL描述符合设计规范的要求,代码覆盖率较好,所提方法在解决大规模问题时效率有所提升,尤其是对于可满足性问题,效率提升非常显著。

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

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

布尔不可满足子式的求解方法研究进展

解释布尔公式不可满足的原因在诸如形式化验证与电子设计自动化等众多领域中都具有非常重要的理论与应用价值.不可满足子式能够为布尔公式不可满足的原因提供精确的解释,帮助应用领域的自动化工具迅速定位错误,诊断问题失败的本质缘由.针对近年来出现的许多求解布尔不可满足子式的研究工作,根据算法的类型归类比较,对各种求解方法进行了概述评论,并简要介绍了在该领域所做的一些研究工作.最后讨论了布尔不可满足子式的求解方法目前面临的主要挑战,并对今后的研究方向进行了展望.

一次性求解多个SAT问题

在实际应用中通常需要求解对应CNF(Conjunctive Normal Form)公式之间仅相差几个子句的一系列SAT(Satisfiability Problem)问题,但目前绝大多数SAT求解算法都是针对单一SAT问题设计的。为此,基于DPLL提出了nDPLL算法,并在随机问题上对该算法的效率进行测试。实验结果表明,nDPLL算法能一次性求解多个SAT问题,对于特定范围的CNF公式集具有较高的效率,CNF公式集的规模越大、相近因子越高、子句数和变量数的比值越大,则nDPLL算法的效率越高。