BDD
二分決定グラフ
論理関数 = 0/1の組み合わせに対して0/1を返す物
論理関数をBDDで表せる
https://gyazo.com/ce01d2c01a9cfc4de3b0b783ed39203d
https://ja.wikipedia.org/wiki/二分決定図 より
BDDで、AND, OR, XORなどが表現できる
変数の数nに比例する大きさのBDDになる
最後の出力の0と1を置き換えてあげれば、NAND, NORなども表現できる
BDDは、変数の順序によってもサイズが大きく変わる
BDDは、簡約化・圧縮できる
https://gyazo.com/c0107b3ace7dd8cb5c73b3a71f27a463
https://www-alg.ist.hokudai.ac.jp/~thomas/publications/sigfpai06imz.pdf より
左が論理関数をそのまま木(BDT)にしたもの、それを真ん中の図(BDD)のように圧縮できる
右はZDD（後述）
ZDD(ゼロサプレス型BDD)
通常の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を使う
blu3mo.iconn=26までの世界記録を争う話がすごい楽しそうw
#離散アルゴリズム
情報科学の達人.icon