代码之家 › 专栏 › 技术社区 › Jules

SAT学习材料(布尔可满足性问题)【关闭】

sat-solvers computer-science

3

Jules · 技术社区 · 14 年前

在SAT(Boolean Satisfiability Problem)求解器上,哪些文档值得阅读?我没能通过谷歌找到好的资料。我找到的文件要么是鸟瞰图,要么太高级,要么是损坏的PDF文件…

您建议学习现代实用SAT解算器中的算法的哪些论文/文档?

2 回复 | 直到 9 年前

1

8

Thomas Leonard 11 年前

那你就可以看迷你报纸了 "An Extensible SAT-solver" .

你也应该阅读 "GRASP - A New Search Algorithm for Satisfiability" 了解minisat中使用的冲突驱动学习算法。

我可以很容易地使用这些资源在Python中编写SAT解算器。我的 sat.py 代码是可用的(目前是lgpl 2.1),但它是最近的,所以可能仍然包含bug。它缺乏一些来自minitat设计的优化;如果您想要原始速度,请使用minitat代码;-)

更新:我还做了一个OCAML版本, sat.ml ,这样可以更容易地看到类型。

2

0

noctua 9 年前

一本好书是:Uwe Sch_《宁》;Jacobo Tor_n——满足性问题