如何高效实现二元决策图（BDD）？
有关二元决策图的背景信息可以在维基百科上的 BDD 找到。
最简单的方法是构建 BDT（二元决策树），然后根据两个规则减少它：
- 合并任何同构子图。
- 消除两个子节点同构的任何节点。
但有一个主要问题，与 BDD 相比，BDT 可能非常巨大。有没有办法在不先构建 BDT 的情况下构建 BDD？
Background about binary decision diagrams can be found here BDD on wikipedia.
The simplest approach is to build BDT (Binary Decision Tree) and then reduce it due to two rules:
- Merge any isomorphic subgraphs.
- Eliminate any node whose two children are isomorphic.
But there is one major problem BDT can be really huge in comparison to BDD. Is there any way to build BDD without building BDT first?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
使用 安徒生，第 16-17 页。我有一段时间没有使用 BDD，但我相信 H 或 T 应该是一个哈希表。为了安全起见，使用哈希表。
Use the
Mk(make node) andBuild(construct BDD) algorithms from Andersen, pp. 16-17. I haven't played with BDDs in a while, but I believe either H or T should be a hash table. Use hash tables for both to be on the safe side.构建 BDD 的方法是从表示您尝试构建的布尔函数的表达式的解析树开始。
也就是说，如果你想要 (A+B).(C+D) 的 BDD，你首先将 (A+B).(C+D) 解析成一棵树：
然后递归地构建 BDD - 你需要可以形成的方法两个 BDDS 的 AND 和 OR，以及基本情况（单变量 BDD）。
这对于逻辑电路也同样有效（视为解析 DAG 而不是树）。
这些关于 BDD 的注释解释了如何实现 AND 和 OR，以及使事情高效工作所需的哈希表：http://bit .ly/cuClGe
The way to build the BDD is from the parse tree for the expression representing the Boolean function you are trying to build.
I.e., if you want the BDD for (A+B).(C+D), you first parse (A+B).(C+D) into a tree:
then build the BDD recursively - you need methods that can form the AND and the OR of two BDDS, and the base case (single variable BDD).
This works just as well for logic circuits too (view as a parse DAG instead of tree).
These notes on BDDs explain how to implement AND and OR, also the hashtables that are needed to make things work efficiently: http://bit.ly/cuClGe
如果你想做得正确，请尝试阅读高德纳 (Knuth) 的作品。
https://www-cs-faculty.stanford.edu/~ knuth/fasc1b.ps.gz
更准确地说，该书章节第 14 页开始的算法“R”是对 OP 的精确而完整的答案；
Knuth 的书籍章节是一本非常好的深入参考书，碰巧他写了一个关于 (RO)BDD 的章节，这对于任何认真尝试实现 BDD 的人来说都是非常幸运的。
Try to read Knuth, if you want to do it right.
https://www-cs-faculty.stanford.edu/~knuth/fasc1b.ps.gz
To be more precise, the algorithm "R" starting page 14 of that book chapter is a precise and complete answer to the OP;
Overall Knuth's book chapters are a very good in depth reference, it so happens he wrote one on (RO)BDD, which is extremely lucky for anyone seriously trying to implement BDD.