変数の順序付け
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2017/03/06 16:02 UTC 版)
BDDのサイズは、表現しようとする関数とその変数（引数）の順序をどうするかで決定される。BDDのサイズは変数の個数に対して、線形のオーダーから指数のオーダーまで様々である。 f ( x 1 , … , x n ) {\displaystyle f(x_{1},\ldots ,x_{n})} というブール関数があったとき、これを二分決定図に表現する際に、根となるノードからどういう順番で変数を対応させるかによって、そのサイズは指数オーダー（2n）にも線形オーダー（n）にもなる。例えば、 f ( x 1 , … , x 2 n ) = x 1 x 2 + x 3 x 4 + ⋯ + x 2 n − 1 x 2 n {\displaystyle f(x_{1},\ldots ,x_{2n})=x_{1}x_{2}+x_{3}x_{4}+\dots +x_{2n-1}x_{2n}} という形式のブール関数を考える。変数の順序付けを x 1 < x 3 < ⋯ < x 2 n − 1 < x 2 < x 4 < ⋯ < x 2 n {\displaystyle x_{1}<x_{3}<\dots <x_{2n-1}<x_{2}<x_{4}<\dots <x_{2n}} とすると、この関数を表現する BDD のノード数は 2 n + 1 {\displaystyle 2^{n+1}} となる。しかし、 x 1 < x 2 < x 3 < x 4 < ⋯ < x 2 n − 1 < x 2 n {\displaystyle x_{1}<x_{2}<x_{3}<x_{4}<\dots <x_{2n-1}<x_{2n}} という順序付けにすると、ノード数は 2 n {\displaystyle 2n} で済む。 従って、このデータ構造を実際に利用する際には変数の順序付けが非常に重要となる。最良の順序付けを見つける問題はNP困難であることが分かっている。任意の1より大きい定数 c について、最適な解の c 倍のサイズを持つOBDDを生成する順序付けを探す問題もNP困難である。ただし、最適な順序付けを探すための効率的なヒューリスティックが存在する。 (Topological Sort, MinFillなど) 変数の順序をどう変えても常に指数オーダーとなる関数（変数順序付けに依存しない関数）も存在する。例えば、二進数の乗算がそのような関数の例である。BDD から派生したグラフ構造として、二分モーメント図(BMD)やゼロサプレス決定図(ZDD)がある。
※この「変数の順序付け」の解説は、「二分決定図」の解説の一部です。
「変数の順序付け」を含む「二分決定図」の記事については、「二分決定図」の概要を参照ください。
- 変数の順序付けのページへのリンク
