random - SAT 解决 : DPLL vs. ?

Question

现在我正在写关于 SAT 解决问题的文章，但我卡在了一个点上。我希望你能帮助我。

我想描述一些解决 SAT 问题的方法。现在我有三种不同的方式:

1. 暴力破解
2. 随机(幼稚)
3. DPLL(具有不同的启发式)
4. >？失踪了？
5. ...

我的问题是唯一有效的算法是 DPLL(以及其他一些与 DPLL 略有不同的算法)。因此我没有什么可以与 DPLL 进行比较的。

我的问题:如果您能告诉我一些不基于 DPLL (DP) 的算法，我可以将其与之进行比较，那就太好了。

以下是我发现的一些，但无法决定它们是否是一个不错的选择，或者是否有更好的选择:

• 莫尼恩-斯佩肯迈尔
• Dantsin、Goerdt、Hirsch 和 Schöning
• Paturi-Pudlák-Zane-算法
• 霍夫迈斯特、舍宁、舒勒和渡边

感谢您的帮助。

Answer 1

目前最先进的 sat 求解器使用基于 DPLL 的 CDCL(冲突驱动子句学习)。