估算简化有序二叉决策图效率的启发式方法？

Question

10

约简有序二叉决策图（ROBDD）是一种有效的数据结构，用于具有多个变量f（x1，x2，...，xn）的布尔函数。我想要了解它们的效率究竟有多高。

例如，对于数据压缩，我们知道熵低的数据（某些符号出现比其他符号更频繁，重复出现多次）可以被很好地压缩，而完全随机的数据则无法被压缩。

是否有类似的直觉来估计ROBDD能够表示给定布尔公式的效率？这方面的任何文献（最好在线）？

- Heinrich Apfelmus

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Daniel · Accepted Answer

在维基百科的文章中《具有有序二进制决策图的符号布尔操作》，有一篇论文给出了某些函数类（对称的、代表二进制算术）的下限和上限。我认为在平均情况下，2n*log n >= 2^k成立，其中n是图中节点的数量，k是函数的变量数量。上限是n <= 2^(k+1) - 1，用完全二叉树实现。