情報の劣化

• 昨日、ZDDでクリークを列挙する話を書いた
• グラフ情報(隣接関係の情報)からクリークを列挙するのは大変だ
• その大変さは、0/1のべき乗をZDD化するより、グラフ情報からZDD化する方が難しい(らしい)ことと関係しそうだ
• 超立方格子上の点のハミング距離に適当に閾値を与えて、その閾値を基準に格子上の点の間にエッジを引いたようなグラフを考える
• 超立方格子上の点の集合は0/1で表されていて、ZDD化が比較的簡単のようだ
• グラフを作ってそれにZDDを作るのは難しくなる
• これは、格子上の点集合のときにはの0/1情報があるのに、グラフにするとの0/1情報になるからのようだ
• 超立方格子上の点の間の距離を閾値以下で1にするという作業が不等式を用いているから、情報の劣化をもたらしている、とも言える
• では、何かしらの情報があって、それが距離空間にあるとき、点間距離をとってグラフ化するという作業は、情報を落として、理解しやすくしているという面もあるが、ZDD的情報圧縮(これも理解しやすくする処理)にとっては、「面倒を生ん」でいると言えるかもしれない
• そんなときは、グラフにしないで、もとの距離空間座標のままでZDD化するように試みる、というのはどうだろうか・・・
• もう一つの道は、0/1〜ブール演算を利用したZDDだから超立方格子との相性がよいわけで、グラフ〜ハイパーグラフ〜組合せに関しては、0/1以外の整理方法がある(それは分岐木の形をとっていない)のかもしれない
• 0/1でないということは計算機の得意分野ではない、ということなのかもしれない