什么是 SAT（布尔可满足性问题）求解器的好文档。我无法通过谷歌找到好的材料。我发现的文件要么是鸟瞰图，要么是太高级或损坏的 PDF 文件......
您推荐哪些论文/文档来了解现代实用 SAT 求解器中的算法？
问问题
3234 次
2 回答
8
维基百科上的Davis-Putnam-Logemann-Loveland 页面有一个很好的概述。
然后你应该能够关注 minisat 论文“An Extensible SAT-solver”。
您还应该阅读“GRASP - 一种新的可满足性搜索算法”以了解 minisat 中使用的冲突驱动学习算法。
使用这些资源，我可以很容易地用 Python 编写一个 SAT 求解器。我的sat.py代码可用（目前为 LGPL 2.1），但它是最近的，因此可能仍包含错误。它缺少 minisat 设计的一些优化；如果您想要原始速度，请使用 minisat 代码；-)
更新：我还制作了 OCaml 版本sat.ml，这可能更容易查看类型。
于 2010-03-28T10:46:03.277 回答
0
一本好书是：Uwe Schöning；Jacobo Torán - 可满足性问题
于 2015-06-24T17:37:04.880 回答