如何高效地实现二叉决策图（BDD）？

Question

关于二叉决策图的背景可以在这里找到维基百科上的BDD。

最简单的方法是构建BDT（二叉决策树），然后根据以下两个规则进行缩减：
- 合并所有同构子图。
- 消除其两个孩子同构的任何节点。
但是，与BDD相比，BDT可能非常庞大。有没有什么方法可以在不先构建BDT的情况下构建BDD呢？

- Tomek Tarczynski

---

你从未构建过不共享的决策树。BDT仅是解释BDD的一种方式。 - Pascal Cuoq

由于这里涉及到的bdd意义与bdd标签不同，我将删除该标签。 - Don Roby

可以在此处找到各种语言中现有的二叉决策图实现列表（约50个）：https://github.com/johnyf/tool_lists/blob/master/bdd.md。 - 0 _

Answer 1

使用Andersen的第16-17页中的Mk（创建节点）和Build（构建BDD）算法。虽然我已经有一段时间没有使用BDD了，但我相信H或T应该是哈希表。为了保险起见，两者都要使用哈希表。

- Fred Foo

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。

- user486972

Answer 3

如果你想做得对，就试着读一下高德纳。

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

更准确地说，该书第14页开始的算法“R”是对原帖的精确而完整的回答。

总的来说，Knuth的书籍章节是非常好的深度参考资料，碰巧他写了一本关于（RO）BDD的书，这对于任何认真尝试实现BDD的人来说都是非常幸运的。

- Yann TM