Hei*_*mus 9 compression computer-science data-structures binary-decision-diagram
简化有序二元决策图(ROBDD)是多变量布尔函数的有效数据结构f(x1,x2,...,xn).我想获得一个直觉如何,他们是有效的.
例如,对于数据压缩,我们知道具有低熵的数据(一些符号比其他符号更频繁地出现,多次重复)可以很好地压缩,而完全随机数据不能被压缩.
是否有类似的直觉来估计ROBDD如何有效地表示给定的布尔公式？有关此主题的任何文献(最好是在线)？
维基百科文章符号布尔操作与有序二元决策图中有一篇论文给出了某些函数类的下限和上限（对称，表示二进制算术）。我认为在平均情况2n*log n >= 2^k下，其中n是图中的节点数，k是函数的变量数。上限是n <= 2^(k+1) - 1通过完整二叉树实现的。