估计降序二元决策图效率的启发式方法？
降序二元决策图 (ROBDD) 是多变量布尔函数的高效数据结构<代码>f(x1,x2,...,xn)。我想直观地了解它们的效率。
例如，对于数据压缩，我们知道低熵数据（某些符号出现的频率比其他符号多，重复次数多）可以很好地压缩，而完全随机的数据则无法压缩。
是否有类似的直觉来估计 ROBDD 表示给定布尔公式的效率？有关于这个主题的文献吗（最好是在线的）？
Reduced Ordered Binary Decision Diagrams (ROBDD) are an efficient data structure for boolean functions of multiple variables f(x1,x2,...,xn). I would like to get an intuition for how efficient they are.
For instance, for data compression, we know that data with low entropy (some symbols appearing more often than other, many repetitions) can be compressed very well while completely random data cannot be compressed.
Is there an analogous intuition for estimating how efficiently ROBDDs can represent a given boolean formula? Any literature on this subject (preferably online)?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
维基百科文章中有一篇文章 使用有序二元决策图进行符号布尔操作 它给出了某些函数类的下限和上限（对称，表示二进制算术）。我认为在平均情况下
2n*log n >= 2^k成立，其中n是图中的节点数，kcode> 是函数的变量数量。上限是使用完整二叉树实现的n <= 2^(k+1) - 1。There is paper in the Wikipedia article Symbolic Boolean Manipulation with Ordered Binary Decision Diagrams which gives lower and upper bounds for certain function classes (symmetric, representing binary arithmetic). I think that in the average case
2n*log n >= 2^kholds, wherenis the number of nodes in the diagram andkis the number of variables of the function. The upper bound isn <= 2^(k+1) - 1achieved with the full binary tree.