iwiwi 備忘録

学んだことを殴り書きます。自分向けのメモです。

BDD, ZDD, フロンティア法, Graphillion

詳しい資料へのポインタを示しつつ，自分が読んで理解した範囲の簡潔なまとめを書きます．

BDD 入門

湊先生の授業が詳しく分かりやすい． http://www-alg.ist.hokudai.ac.jp/~minato/alg2013.html

  • 概念自体
    • 図を一個見れば一発で理解できる
    • DAG で，各中間ノードは変数で，その変数の値に応じて次に進む子を選ぶ．終着点が答え．
  • 構築法
    • 順序付き既約 BDD (ROBDD) を普通作るらしい．重要な性質を持つらしい．
    • 順序付き ＝ 変数が出現してくる順番が全順序
    • 以下の 2 つのルールを適用し続けていれば既約になる（適用順関係なし）
      • 冗長な接点を全て削除
      • 等価な接点を全て共有
    • 実際には，BDD の間の二項論理演算を繰り返して構築する
  • BDD 同士の演算 (Family Algebra)
    • and, or, xor, not, ... みたいな色々な BDD 同士の演算ができる，便利
  • BDD のサイズと順序
    • 大体３通りらしい
      • 順番に関わらず小さい
      • 良い順序にすれば小さい
      • どう頑張っても大きい（算術乗算，除算，ランダム）
    • DP，局所探索

Javascript で BDD をすぐ作ってくれるサイト http://blog.vjeux.com/2011/project/javascript-binary-decision-diagram.html

ZDD 入門

調度よさそうな資料を発見できなかったので仕方なく Knuth 本を超斜め読みした． http://www.amazon.com/dp/0321580508/ （ドラフトは無料 http://www-cs-faculty.stanford.edu/~knuth/fasc1b.ps.gz）

  • ZDD とは？
    • BDD では，変数 x_i の子が x_j (i<j) であれば，そこに行く時，x_{i+1}, x_{i+2}, ..., x_{j-1} の値は関係なし (don't care)
    • ZDD では，変数 x_i の子が x_j (i<j) であれば，そこに行く時，x_{i+1} = x_{i+2} = ... = x_{j-1} = 0．
    • 自分の理解では，差はこれだけ（だがこの差が性能面で重要になってくる）
  • BDD で行えるような様々な処理は ZDD でも少しの変更で大体行えるっぽい

ZDD の利点について，湊先生の文章． http://w2.gakkai-web.net/gakkai/ieice/vol4no3pdf/vol4no3_224.pdf

  • 特に，疎な部分集合族を表現するのに適している
    • 疎なときに，BDD に比べて一気にノード数が削減できる
    • 平均サイズが 1% の時，100 倍コンパクトになるかも
  • 定数倍の意味を除けば，最悪の場合でも線形リスト等で表現したときと同じメモリ消費量
  • それでいて，BDD 同様 ZDD 同士の演算がそのままできる（Family Algebra）

フロンティア法，Graphillion

フロンティア法についてはこの講義資料が分かりやすい． http://www-lsm.naist.jp/~jkawahara/frontier/frontier_lec.pdf

  • パスを列挙することを考えよう（始点と終点が指定された s-t パス）
  • パスを辺の部分集合として表現，部分集合族を ZDD で管理
    • 辺の順番を適当に決め（BFS とか），その順を変数順にする
    • 辺を順番に ZDD に加えていく，ZDD を上から作っていく
  • 共通部分の判定を，フロンティアに関する mate 配列を使ってやる
    • ZDD の子の部分がまだ無いので，共通してるかどうか分からないけど，共通してるなら縮約しないといけない
    • そこで，「共通している ⇔ フロンティアに関する mate 配列が等しい」
    • プログラミングコンテストでよくやるビット DP とかメモ探索とかと同じ．グラフの bandwidth が出てくるやつ（bandwidth という用語は何故か見かけない）．

Graphillion の中身については，このテクニカルレポートが詳しい（本当は，こっちを先に見てフロンティア法を調べた）． http://www-alg.ist.hokudai.ac.jp/~thomas/TCSTR/tcstr_13_65/tcstr_13_65.pdf

  • 対応しているのは
    • tree, forest, path, cycle, clique, connected component
    • （全部，辺で扱うのかな？ 頂点でやったほうが適切そうなものもあるように感じるけどうまくいかないんだろうか）

その他の *DD

その他の情報へのポインタ http://www.ai-gakkai.or.jp/my-bookmark_vol27-no5/