遺伝学・遺伝統計学関連の姉妹ブログ『ryamadaの遺伝学・遺伝統計学メモ』
京都大学大学院医学研究科ゲノム医学センター統計遺伝学分野のWiki
講義・スライド
医学生物学と数学とプログラミングの三重学習を狙う学習ツール
駆け足で読む○○シリーズ
ぱらぱらめくるシリーズ
カシオの計算機
オンライン整数列大辞典

ZDD:ぱらぱらめくる『クヌース本4.1』

ZDD ぱらぱらめくるシリーズ R
  • ZDD:ゼロ抑制BDD
  • 組合せ論で力を発揮する
  • \botに行きつく経路が多いときに有用である
  • BDDと違う点
    • 節点の解釈が違う
    • 終点は\botはないこともある
    • 節点からの２本のエッジが同一のノードに接続することもある
    • 節点数が節約されることがある
    • BDDではノードが「Primitiveな配列(bead)」に対応したが、ZDDではノードが「別のもの(zead)」に対応する
  • 節点の解釈について
    • \{1,2,...,n\}の部分集合の属を凝縮した表現になっている
  • ZDDのノードが対応するzeadについて