SAT 解决：DPLL vs.？
SAT-Solving: DPLL vs.?
现在我正在写关于 SAT 解决问题的文章，但我卡在了一个点上。我希望你能帮助我。
我想描述一些解决 SAT 问题的方法。现在我有三种不同的方式：
- 暴力破解
- 随机（幼稚）
- DPLL（具有不同的启发式）
- ？不见了？
- ...
我的问题是唯一有效的算法是 DPLL（以及其他一些与 DPLL 略有不同的算法）。因此我没有什么可以与 DPLL 进行比较的。
我的问题：如果您能告诉我一些不基于 DPLL (DP) 的算法，我可以将其与之进行比较，那就太好了。
以下是我找到的一些，但无法确定它们是否是一个不错的选择，或者是否有更好的选择：
- Monien-Speckenmeyer
- Dantsin、Goerdt、Hirsch 和 Schöning
- Paturi-Pudlák-Zane-算法
- 霍夫迈斯特、舍宁、舒勒和渡边
感谢您的帮助。
最先进的卫星求解器目前使用基于 DPLL 的 CDCL（冲突驱动子句学习）。
在您建议的 SAT 求解算法中，bruteforce 和 DPLL 都是完整的算法，如果有足够的时间，可以保证找到令人满意的分配或证明问题不可满足。正如 Million 提到的，CDCL，DPLL 的进步，也已经完成。
如果您想讨论替代方案，我建议您查看不完整的算法。这些通常基于随机本地搜索，包括 GSAT 和 WalkSAT。虽然这些算法不能保证找到答案，但它们传统上非常擅长解决随机（相对于工业）SAT 问题。它们还被用于解决比任何实施基于 DPLL 算法的求解器能够解决的更大的 SAT 问题。
为了进一步研究，我推荐 Biere 的精彩著作 'Handbook of Satisfiability'。
现在我正在写关于 SAT 解决问题的文章，但我卡在了一个点上。我希望你能帮助我。
我想描述一些解决 SAT 问题的方法。现在我有三种不同的方式：
- 暴力破解
- 随机（幼稚）
- DPLL（具有不同的启发式）
- ？不见了？
- ...
我的问题是唯一有效的算法是 DPLL（以及其他一些与 DPLL 略有不同的算法）。因此我没有什么可以与 DPLL 进行比较的。
我的问题：如果您能告诉我一些不基于 DPLL (DP) 的算法，我可以将其与之进行比较，那就太好了。
以下是我找到的一些，但无法确定它们是否是一个不错的选择，或者是否有更好的选择：
- Monien-Speckenmeyer
- Dantsin、Goerdt、Hirsch 和 Schöning
- Paturi-Pudlák-Zane-算法
- 霍夫迈斯特、舍宁、舒勒和渡边
感谢您的帮助。
最先进的卫星求解器目前使用基于 DPLL 的 CDCL（冲突驱动子句学习）。
在您建议的 SAT 求解算法中，bruteforce 和 DPLL 都是完整的算法，如果有足够的时间，可以保证找到令人满意的分配或证明问题不可满足。正如 Million 提到的，CDCL，DPLL 的进步，也已经完成。
如果您想讨论替代方案，我建议您查看不完整的算法。这些通常基于随机本地搜索，包括 GSAT 和 WalkSAT。虽然这些算法不能保证找到答案，但它们传统上非常擅长解决随机（相对于工业）SAT 问题。它们还被用于解决比任何实施基于 DPLL 算法的求解器能够解决的更大的 SAT 问题。
为了进一步研究，我推荐 Biere 的精彩著作 'Handbook of Satisfiability'。