9

縮小順序二分決定図（ROBDD）は、複数の変数のブール関数の効率的なデータ構造ですf(x1,x2,...,xn)。それらがどれほど効率的であるかを直感的に理解したいと思います。

たとえば、データ圧縮の場合、エントロピーが低いデータ（一部のシンボルが他のシンボルよりも頻繁に出現し、多くの繰り返しが発生する）は非常によく圧縮できますが、完全にランダムなデータは圧縮できません。

ROBDDが特定のブール式をどれだけ効率的に表すことができるかを推定するための類似した直感はありますか？この主題に関する文献（できればオンライン）はありますか？

4

1 に答える 1

4

ウィキペディアの記事に、特定の関数クラス（対称、二分決定図を表す）の下限と上限を示す順序付き二分決定図を使用したシンボリックブール操作に関する論文があります。2n*log n >= 2^k平均的な場合は成り立つと思います。ここnで、は図のノードのk数であり、は関数の変数の数です。上限はn <= 2^(k+1) - 1完全な二分木で達成されます。

于 2010-08-18T13:58:00.137 に答える