关于二元决策图的背景可以在维基百科上的 BDD中找到。
最简单的方法是构建 BDT（二元决策树），然后根据两个规则对其进行缩减：
- 合并任何同构子图。
- 消除两个孩子同构的任何节点。
但是有一个主要问题 BDT 与 BDD 相比可能非常大。有没有办法在不先构建 BDT 的情况下构建 BDD？
问问题
6777 次
3 回答
6
使用来自AndersenMk的(make node) 和Build(construct BDD) 算法，第 16-17 页。我有一段时间没有玩过 BDD，但我相信H或T都应该是哈希表。为了安全起见，两者都使用哈希表。
于 2010-11-02T11:13:26.947 回答
1
构建 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
于 2010-11-02T15:18:43.837 回答
-1
如果你想做对的话，试着阅读 Knuth。
https://www-cs-faculty.stanford.edu/~knuth/fasc1b.ps.gz
更准确地说，该书章节的第14页开始的算法“R”是对OP的精确而完整的答案；
总体而言，Knuth 的书章节是一个非常好的深度参考，碰巧他写了一篇关于 (RO)BDD 的文章，这对于任何认真尝试实施 BDD 的人来说都是非常幸运的。
于 2018-05-24T19:59:28.027 回答