BDD

Last updated Dec 16, 2022 Edit Source

• 二分決定グラフ

• 論理関数 = 0/1の組み合わせに対して0/1を返す物

• 論理関数をBDDで表せる

  • 
    • https://ja.wikipedia.org/wiki/二分決定図 より

• BDDで、AND, OR, XORなどが表現できる

  • 変数の数nに比例する大きさのBDDになる
  • 最後の出力の0と1を置き換えてあげれば、NAND, NORなども表現できる

• BDDは、変数の順序によってもサイズが大きく変わる

• BDDは、簡約化・圧縮できる

  • 
    • https://www-alg.ist.hokudai.ac.jp/~thomas/publications/sigfpai06imz.pdf より
    • 左が論理関数をそのまま木(BDT)にしたもの、それを真ん中の図(BDD)のように圧縮できる
    • 右はZDD（後述）

• [ZDD]

  • 通常のBDDと少し違う圧縮方法
    • 少し違うというか、BDDより多くのものを圧縮する
  • BDDの圧縮基準に加え、1の場合に最終出力0に向かう場合もその変数自体を消しちゃう
    • つまり、何が冗長か、の定義がBDDと違う
    • 上の図の右のグラフ
  • 最終出力が1の場合のみ気にしたい場合に有効
    • ex: 商店の購買データ
  • 疎な集合（ほとんどの到着点が0）の場合に著しい効果が出る（コンパクトに表現できる）

• 一言でいうと

  • BDD: Dont’careを省略、密な論理関数に向いてる
  • ZDD: 負の出現を省略、疎な論理関数に向いてる

• 論理関数からBDD(もしくはZDD)を作りたい場合

  • BDTを作ってから圧縮すれば、当然作れる
  • ただ、この圧縮を毎回やってると計算量/メモリ量が大変なことになる
  • なので、直接論理式から圧縮されたBDDを生成したい
  • やりかた
    • ボトムアップ方式: 各変数を小さいBDDとして、二つのBDD同士をAND,NOT,OR演算で組み合わせて最終的なBDDを作る
    • トップダウン方式: BDTを作る過程で、（1を使った回数を数えたりして）作りながら圧縮していく
      • フロンティア法

• 離散構造処理技術のフレームワーク上では、BDD,ZDD等の決定グラフは「索引構造」にあたる

  • 論理演算、数え上げ、線形関数最大化、サンプリングなどの「基本演算」のやりかた
    • shannon decompositionで分解して、常に1/0を返す$f$にたどり着くまで再帰的に演算していく
    • Shannon Decomposition: $f_a = (\lnot x_i \land f_{a0}) \lor (x_i \land f_{a1})$
      • 要は、二分木の一分岐を数学的に表したもの
      • $f_a$と$f_{a\prime}$の演算を、decompositionした上で再帰的にうことができる

• 応用先

  • 初期は集積回路の設計問題のためのアルゴリズム
  • 最近は処理能力の向上によって、めちゃでかいBDDが扱えるように
    • 経路探索
    • スーパーマーケットの売り上げデータから良く売れる商品パターンを探す
    • 交通事故データーから危険な要素の組み合わせを調べる
  • 組み合わせ爆発お姉さん問題の解法もZDDを使う
    • n=26までの世界記録を争う話がすごい楽しそうw #離散アルゴリズム