data-structures - 用于估计降阶有序二元决策图效率的启发式方法？

Question

Reduced Ordered Binary Decision Diagrams(ROBDD)是一种有效的数据结构，用于多个变量f(x1,x2,...,xn)的 bool 函数。我想对它们的效率有个直觉。

例如，对于数据压缩，我们知道熵值低的数据(某些符号比其他符号出现频率更高，很多重复)可以被很好地压缩，而完全随机的数据则不能被压缩。

是否存在类似的直觉来估算ROBDD可以如何高效地表示给定的 bool 公式？有关于此主题的文献(最好是在线文献)吗？

Answer 1

Wikipedia文章Symbolic Boolean Manipulation with Ordered Binary Decision Diagrams中有一篇论文，其中给出了某些函数类(对称，表示二进制算术)的上下限。我认为在通常情况下2n*log n >= 2^k成立，其中n是图中的节点数，而k是该函数的变量数。上限是使用完整的二叉树实现的n <= 2^(k+1) - 1。