- 日本語総説はこちら
- 組合せ発散に対する、この方法の効果はこちらの動画と実行例コードで
- BDD:binary decision diagram
個の2分岐が
の場合を作る。それを表したのが二分決定木(binary decision tree)
- BDDは二分決定木を簡略したグラフ
の3分岐の「○、×」が作る
の場合のうち、
の2通りが「あり」だという情報があるとする。
というように
のべき集合の2つの要素の集合(『組み合わせ集合』)とみなすこともできる
- ZDD:zero-suppressed bdd
- seqBDD
- 組合せ集合に向いているのがZDDなら、順列集合に向いているものがあってもよい
- それがseqBDD
- BDD/ZDD/seqBDDの代数系
- ダイアグラムができても、それをハンドリングするのが便利でないと、使いにくい
- 特に組合せ発散対策ならなおのこと
- そのための「ハンドリング」ツールが「BDD/ZDD/seqBDDの基本演算(とそれが作る代数構造)」
- いわゆる集合演算が、計算機処理的な色を付けて拡張されたもの
- この話題の周辺のことで、メモしておきたいこと
- BDD/ZDD/seqBDDの応用
- ZDDによるパス列挙
- Kunuth先生によるSimpath
- ZDD演算規則を介さずにZDDを作成(こちら)
- 言語解析にseqBDD(こちら)
- 単体のZDD
を要素全体としたときに
で表される単体に対応するZDD
- ZDDによるパス列挙
遺伝学・遺伝統計学関連の姉妹ブログ『ryamadaの遺伝学・遺伝統計学メモ』
京都大学大学院医学研究科ゲノム医学センター統計遺伝学分野のWiki
講義・スライド
医学生物学と数学とプログラミングの三重学習を狙う学習ツール
駆け足で読む○○シリーズ
ぱらぱらめくるシリーズ
カシオの計算機
オンライン整数列大辞典