如何有效地实现二元决策图（BDD）？

Question

关于二元决策图的背景可以在这里找到BDD on wikipedia。

最简单的方法是构建BDT（二进制决策树），然后根据两个规则减少它： - 合并任何同构子图。 - 消除两个孩子同构的任何节点。 但是与BDD相比，BDT存在一个主要问题。有没有办法在不首先构建BDT的情况下构建BDD？

Answer 1

使用Mk的Build（make node）和Andersen（构造BDD）算法，第16-17页。我有一段时间没有使用BDD，但我相信H或T应该是哈希表。使用哈希表两者都是安全的。

Answer 2

构建BDD的方法来自表示您尝试构建的布尔函数的表达式的解析树。

即，如果你想要（A + B）。（C + D）的BDD，你首先解析（A + B）。（C + D）到树：

   .
  / \
 +   +
/ \ / \
A B C D

然后递归地构建BDD - 您需要可以形成两个BDDS的AND和OR的方法，以及基本情况（单个变量BDD）。

这也适用于逻辑电路（视图为解析DAG而不是树）。

关于BDD的这些注释解释了如何实现AND和OR，以及使事情有效工作所需的哈希表：http://bit.ly/cuClGe

Answer 3

如果你想做正确的话，试着阅读Knuth。

https://www-cs-faculty.stanford.edu/~knuth/fasc1b.ps.gz

更确切地说，从该书章节的第14页开始的算法“R”是对OP的精确和完整的答案;

整体Knuth的书籍章节是一个非常好的深度参考，它恰好在（RO）BDD上写了一个，这对于任何认真尝试实施BDD的人来说都是非常幸运的。