简化有序二元决策图(ROBDD) 是一种用于多变量布尔函数的有效数据结构f(x1,x2,...,xn)。我想对它们的效率有一个直觉。
例如，对于数据压缩，我们知道熵低的数据（一些符号出现的频率比其他符号多，重复次数多）可以很好地压缩，而完全随机的数据不能被压缩。
是否有类似的直觉来估计 ROBDD 表示给定布尔公式的效率？关于这个主题的任何文献（最好是在线的）？
问问题
380 次
1 回答
4
Wikipedia 文章Symbolic Boolean Manipulation with Ordered Binary Decision Diagrams中有一篇论文给出了某些函数类的下限和上限（对称，表示二进制算术）。我认为在平均情况下，图中的节点数是2n*log n >= 2^k哪里，函数的变量数是哪里。上限是用完整的二叉树实现的。nkn <= 2^(k+1) - 1
于 2010-08-18T13:58:00.137 回答