代码之家 › 专栏 › 技术社区 › Heinrich Apfelmus

估计降阶二元决策图效率的启发式方法?

binary-decision-diagram computer-science compression data-structures

9

Heinrich Apfelmus · 技术社区 · 15 年前

Reduced Ordered Binary Decision Diagrams (robdd)是多变量布尔函数的有效数据结构 f(x1,x2,...,xn) . 我想要一个直觉怎样他们很有效率。

例如,对于数据压缩,我们知道低熵的数据(一些符号比其他符号更常见,重复次数多)可以很好地压缩,而完全随机的数据不能压缩。

有没有一种类似的直觉来估计robdds如何有效地表示一个给定的布尔公式?有关于这方面的文献吗(最好是网上的)?

1 回复 | 直到 9 年前

1

4

Daniel 15 年前

维基百科上有篇文章 Symbolic Boolean Manipulation with Ordered Binary Decision Diagrams 它为某些函数类(对称的,表示二进制算术)提供下限和上限。我认为一般情况下 2n*log n >= 2^k 持有,在哪里 n 是关系图中的节点数,并且 k 是函数的变量数。上限是 n <= 2^(k+1) - 1 用完整的二叉树实现。