用語解説
以下に本文に出てくる専門用語の補足を羅列する.
次数:グラフの頂点に接合する辺の数(from wiki).
誘導グラフ:部分グラフの一種であり,あるグラフから,一部の頂点を取り出し,その頂点対の辺の有無が元のグラフと一致するグラフ(from wiki).
ノード(node): グラフでいうほぼ頂点(vertex).
アーク(arc):グラフでいうほぼ辺(edge).
bool値:真理値のtrue(真)とfalse(偽)の２つの値のいずれかを取る値.
べき集合:数学において,与えられた集合から,その部分集合の全体として新たに作り出される集合のこと.(from wiki)
例:x=($x_{1},x_{2},x_{3}$)のべき集合は
($\emptyset$,{$x_{1}$},{$x_{2}$},{$x_{3}$},{$x_{1}$,$x_{2}$},{$x_{2}$,$x_{3}$},{$x_{3}$,$x_{1}$},{$x_{1}$,$x_{2}$,$x_{3}$})である.
部分集合:集合Aが集合Bの部分集合であるとは,AがBの一部の要素だけからなること.(from wiki)
例:A={1,2,3},B={1,2}とするとBはAの部分集合.
集合族:集合の要素のみを持つ集合のこと. 例えば, A={1,2},B={2,3},C={3,4}は集合であるが集合族ではない. 一方, D={A,B,C}は集合族である.
作成したプログラム及び入力テキスト
以下のgithubからソースコードと入力テキスト見れる.
適宜参照されたし.
本文の目的
ある集合がある条件下で取りうる「その集合のべき集合の部分集合」をトップダウン法を用いてBDD,ZDDの決定図をつくり, 大規模データにおいても比較的少ない計算量でコンパクトに集合を表現する一般論を示すとともに, その実用例を主にマインスイーパーというゲームを用いて応用する手順を解説する.
イントロ
「遠足のおやつは300円まで」というフレーズを一度は聞いたことがあるのではないだろうか? 300円以下で買える「最高のおやつセット」について考えてみよう.
この「遠足のおやつは300円まで」問題は数学的にとらえるとと以下のように考えられる.
\begin{align}
今あなたはn個のおやつに興味がありそれぞれのおやつの番号を1,2,....,nとしておく.商品番号がi(1 \leqq i \leqq n)のおやつの値段をそれぞれv_{i}, おやつの満足度をw_{i}とする. 合計の価格が300円以内に収まるように商品を買う場合満足度を最大にする組み合わせを求めよ.
\end{align}
(動的計画法を知っている人は知らないふりをして考えてもらうと) この問題の解き方の一つとして商品集合のべき集合を対象とした全探索が考えられる. これはある集合において(n個のおやつの集合において)そのべき集合を列挙し, その要素の内条件を満たす全ての集合の内(つまり予算内に収まる組み合わせの内)最も適した(満足度が最も高くなる)組み合わせを求める最も単純な方法である.
このアルゴリズムで注目したい部分は「べき集合を列挙しそのべき集合のうちある条件を満たす部分集合を求める」という過程である.つまり, この方法で考えなければならない組み合わせはもちろん商品集合のべき集合であり, その集合の個数は$2^{n}$であることが知られている. つまりnが少し増えるだけでその値は爆発的に増加してしまう. 例えば商品数n=2の際, その組み合わせとして考えられるのは {{∅},{1},{2},{1,2}}({∅}は空集合)の4通り, n=3の際は{{∅},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}の8通りに収まるが, n=30の時は約10億通りとおよそ人の手が届かない範囲になり, n=100となったらもはやスーパーコンピューターを駆使しても処理できない領域となる. 自然とこのようなべき集合を考える問題においてシンプルに全探索するより効率的に処理ができる方法を使いたくなる. そんな時に使いたいのが決定図(decision diagram)である.
決定図
決定図とは集合族を有向グラフで表現する方法である.今回の決定図の運用目的としてはx=($x_{1}$,$x_{2}$,..,$x_{n}$)のn種類の要素を持つ集合のべき集合の内ある条件を満たす部分集合を計算量を小さくしながらコンパクトに表現することである.
本文では, 主に使われる2つの決定図であるBDD(Binary-Decision-Diagram,二分決定図), ZDD(Zero-Suppressed-BDD,0を抑制した決定二分図)を紹介し, 最後にトップダウン法を用いたBDD,ZDDの構成手法を紹介する.
二分決定木
決定図の説明の前に二分決定木の導入をする. 二分決定木は「すでに求まったある集合$x=(x_{1},x_{2},....,x_{n},)$のべき集合の部分集合である集合族をグラフ表現する」ために存在する.
二分決定木はノード, アークからなるグラフである. 最も上の層には1つの根ノード, 及び終端部分(最下層部)にはbool値であるTrue or Falseのいずれかが存在する. 非終端ノードはn個の層ラベルからなり, i(1$\leqq$i$\leqq$n)番目の層が$x_{i}$の存在を表し, それぞれ0枝, 1枝と呼ばれる2つの下の層へ伸びる枝を持つ. ゆえに根ノードからある終端ノードへと至る経路でn個の非終端ノードを通るが各i層($1\leqq i \leqq n$)において0枝を通れば$x_{i}$はその経路が表す集合には含まれない, 1枝を通ればその経路が表す集合に含むと考え,経路が示す集合がすでに用意されたある集合族に含まれるのであればその終端ノードはTrue, 逆に含まれなかったらFalseを与えることである集合族を示すグラフを作る.
以下, 決定二分木の具体例.
BDD(Binary-Decision-Diagram,二分決定図)
概要
BDD(二分決定図)は二分決定木のノードを削除と共有をすることでその図が示す集合族を保ちながらコンパクトにした図である. 共有条件と削除条件は以下である.
共有条件
同じ層に存在する2つのノードの0枝と1枝がそれぞれ同じノードを指しているとき, その2つのノードを共有することができる.
削除条件
あるノード$\alpha$の0枝と1枝が同じノード$\beta$を指しているときにそのノードを削除するとともに$\alpha$を削除するとともに$\alpha$を指示していた枝を$\beta$に伸ばす.
この2つの条件を図で表現すると以下のようである.
この共有条件と削除条件を用いて例えば以下の決定二分木をBDDに変換すると次の図のように遷移させることができる.
この図を見るとわかるようにノードの共有が起こることでこのグラフは有向木でなくなるため二分探索木でなく二分探索図(BDD)となる.
二分決定木とBDDの集合表現の違い
二分決定木は根ノードから終端部分に伸びる辺が0枝か1枝かを考えれば最終的に求めたい集合族を得ることができた. しかしながらBDDの集合族のもとめかたは異なり, 論理関数を用いて求めたい集合族を得る. 具体的には次のよう. 根ノードからTrueの終端記号に伸びる経路は一つの論理関数を表しi番目の層のノードが($1\leqq i \leqq n$)1枝であれば$t_{i}$, 0枝であれば$\bar{t_{i}}$とし, それぞれの論理記号の積をその経路の論理関数を表現する. この$t_{i}$はtrueまたはFalseのbool値であり, $x_{i}$の存在で定められている. この論理関数がTrueとなるような$t_{i}$の組み合わせこそが求めたい集合族である. 具体的には上で作成されたBDDが表す集合は以下のように求めることができる.
BDDの集合表現を簡単に述べると,「言及していない要素はその要素を含んでも含まなくてもよく,どちらの場合の集合もBDDが示す集合族の要素」として表現する.
また,この図からわかるように同じ集合を示すグラフでもBDDを用いることでよりノード数が少ないコンパクトなグラフで表現することができる.
ZDD(Zero suppressed BDD)
概要
ZDDは二分決定木のノードを共有や削除することでコンパクトにするという点は同じであるが, その削除方法がBDDと異なる.
共有条件
共有条件はBDDと同じである.
削除条件
あるノード$\alpha$の1枝がFalseを指し示しているとき$\alpha$を削除するとともに$\alpha$を指し示す枝を$\alpha$の0枝が示すノードに向かわせる. つまり, 以下のような図を考えればよい.
集合表現
ZDDが表す集合の求め方は二分決定木と同じである.
この方法を用いれば二分決定木をZDDに変換することができ, 例えば, 上の二分決定木が表すZDDは以下のように変換でき, その集合が示す集合族も確認できるだろう.
このように同じ集合族でも違う表現方法の決定図で表される.
BDDとZDDの問題点
BDDとZDDは集合族をグラフでコンパクトに表現できるという特徴を持つがその前提として二分決定木が必要である. しかしながら, 二分決定木の作成には元の集合の要素数をnとすると終端ノードが$2^{n}$個存在するのでその分の計算量が必要となり, 今回の目的の計算量を小さくするという目的が果たせなくなってしまう.(困った). これらの最初の二分決定木を作る過程は大きな計算量が必要となってしまうので根ノードから下に徐々にグラフを作成していくトップダウン法でBDD,ZDDの混合グラフを作成する手法について紹介していきたい.
トップダウン法
トップダウン法はBDD,ZDDの混合グラフを上から下に決定図を作るという手法である.
以下, トップダウン法で$x=(x_{1},x_{2},....,x_{n})$のべき集合の部分集合を決定図で表現することを目指す. また, 以下$\alpha$は第i層に存在するノードとする.
初期状態と漸化的遷移
初期状態において層ラベル番号が1の根ノードを1つと終端記号TrueとFalseの2つを用意する.
さらに共有条件とノード生成, Trueの枝刈りとFalseの枝刈りという4つの要素でトップダウン法を行う.
集合表現方法
True枝刈り以外では基本ZDDと同じように集合を表現する.
共有条件
問題ごとに「ある集合が解の要素になるか」の条件が存在する. (例えば300円問題なら選んだ商品の値段の総和が300円以下になる) ここで「1番目からi番目の商品の内今考えている組み合わせはその条件を満たせるかどうか」を判定する際に用いる値や配列をはじめとしたある存在をconfiguration(日本語で「様態」)と呼び, あるノード$\alpha$に対してそのconfigurationを$\phi(\alpha)$と書く. ここで同じ層ラベルに存在するノード$\beta$と$\gamma$においてそのcontiguration,つまり$\phi(\beta)$と$\phi(\gamma)$が等しい時, $\beta$と$\gamma$は共有できる.
この共有条件の具体例を上の300円問題を用いて解説していきたい.この300円問題の「ある集合が最終的に求めたいある集合族の要素になるか」の条件は当然,「選んだ商品の合計が300円以内に収まっている」ということである. そこで「1番目からi番目の商品のみを考えた集合がその条件を満たせるかどうか」を判定する際に用いる値は「1番目からi番目までの商品の合計の金額」である. よって$\phi(\alpha)$が示す値は根ノードから$\alpha$ノードまでの経路が示す集合のそれぞれの価値の合計とする. そして, 根ノードからi番目の層ラベルにある$\beta$と$\gamma$までのそれぞれの経路が表す1から商品iまでのある組み合わせ集合の価値の合計である$\phi(\beta)$と$\phi(\gamma)$が等しいとき$\beta$と$\gamma$が共有できる.
以下, あるノード$\alpha$の0枝の終点を$\alpha_{0}$, 1枝の終点を$\alpha_{1}$と表現する.
ノード生成
「ノード生成」過程においてある層ラベルiに存在するノード$\alpha$は0枝と1枝の2つの枝と(i+1)層にその枝の終点ノードを生成し, 0枝の場合はi番目の要素が存在しない場合のcontiguration$\phi(\alpha_{0})$,1枝の場合はi番目の要素が存在する場合のcontiguration$\phi(\alpha_{1})$をそれぞれ作成する. 例えば, 上の「300円問題」の場合について考えると, 層ラベルiに存在するノード$\alpha$の0枝と1枝の終点$\alpha_{0}$と$\alpha_{1}$の$\phi(\alpha_{0})$,$\phi(\alpha_{1})$は$\phi(\alpha_{0})$=$\phi(\alpha)$,$\phi(\alpha_{1})$=$\phi(\alpha)$ + (i番目の商品の値段)と遷移できる. というのもi番目の商品を選ばなかった時は商品の値段の合計は変わらなく, i番目の商品を選んだ場合は商品の値段合計はそれまでの商品合計にi番目の商品の値段を加えたものになるからである.
枝刈り
「枝刈り」とはある探索を行っている最中にある途中の時点で最終的な結果がすでに分かったならばその時点で探索を終了することができるという手法である. 枝刈りの利点はある時点で探索を終了できるという点であり, 無駄なノードを減らし, その下のノードを生成する計算を省くことができるという点で有用である.枝刈りにはTrue枝刈りとFalse枝刈りが存在する.
False枝刈り
層ラベルiにあるノード$\alpha$のb枝(bは0または1)遷移で生成される$\alpha_{b}$の$\phi(\alpha_{b})$を考えた時, 「$\phi(\alpha_{b})$を受け取りTrueまたはFalseを返すようなbool値を返す関数$\textrm{F-prune}(\alpha,b,x_{i})$がTrueを返す時, $\alpha$のb枝の終点をFalseに接続させることができる」ような$\textrm{F-prune}$を作り, $\textrm{F-prune}(\alpha,b,x_{i})$=Trueとなる時, $\alpha$のb枝の終点をFalseに接続させるという操作を「False枝刈り」と呼ぶ.「300円問題」で例を示す. ここで「$\textrm{F-prune}(\alpha,b,x_{i})$がTrueを返す時, $\alpha$のb枝の終点をFalseに接続させる」ことができるような$\textrm{F-prune}(\alpha,b,x_{i})$は$\phi(\alpha_{b})$が300円より大きいときTrueを返し300以下であればFalseを返すような関数であればよい.(ちなみに301円や400円より大きいときTrueを返すような$\textrm{F-prune}$を考えることもできる. しかしながら300円より大きいときTrueを返すような関数が一番ノードを削除できるいい条件である.)
層ラベルi番目にあるノード$\alpha$において$\phi(\alpha)=270$であり, i番目の商品の価値を40円としたときに$\phi(\alpha_{1}) = 270 + 40 = 310$である.この時, $\textrm{F-prune}(\alpha,b,x_{i})=True$であるのでこの時点で$\alpha$の1枝をFalseに接続し, $\alpha$の探索を終了できる.
True枝刈り
あるノード$\alpha$のb枝(bは0または1)遷移で生成される$\alpha_{b}$の$\phi(\alpha_{b})$を考えた時, 「$\phi(\alpha_{b})$を受け取りTrueまたはFalseを返すようなbool値を返す関数$\textrm{T-prune}(\alpha,b,x_{i})$がTrueを返す時, $\alpha$のb枝の終点をTrueに接続させることができる」ような$\textrm{T-prune}$を作り, $\textrm{T-prune}(\alpha,b,x_{i})$=Trueとなる時, $\alpha$のb枝の終点をTrueに接続させるという操作を「True枝刈り」と呼ぶ. また 「True枝刈り」は(i+1)番目以降の要素のべき乗の集合のそれぞれの要素の集合と根ノードから$\alpha$のb枝までの経路が示す集合の集合和の集合がTrueとなるBDD.True枝刈り(以下, この枝刈りの関数を$\textrm{T-prune}(\alpha,b,x_{i}).BDD$)と根ノードから$\alpha$のb枝までの経路が示す集合がTrueとなるZDD.True枝刈り(以下, この枝刈りの関数を$\textrm{T-prune}(\alpha,b,x_{i}).ZDD$)とする. そして,BDD枝刈りを行った際のノード$\alpha$からTrueノードまでの経路はBDDとして集合を表現, ZDD枝刈りを行った際のノード$\alpha$からTrueノードまでの経路はZDDとして集合を表現する.
「300円問題」で例を示す. 「$\textrm{T-prune}(\alpha,b,x_{i}).BDD$がTrueを返す時, $\alpha$のb枝の終点をTrueに接続し」かつ「それ以降の要素のべき集合のそれぞれの要素の集合と根ノードから$\alpha$のb枝までの経路が示す集合の集合和の集合がTrueとなる」 ような$\textrm{T-prune}(\alpha,b,x_{i}).BDD$は, 300-$\phi(\alpha_{b})$がそれ以降のi+1の商品の値段の総和以上であればTrueを返し, そうでなければFalseを返すような関数とすればよい.(これも, 例えば300-$\phi(\alpha_{b})$がそれ以降の商品の価値の総和+1円より大きいという条件も$\textrm{T-prune}.BDD$=Trueとなる条件となる. しかし300-$\phi(\alpha_{b})$がそれ以降のi+1の商品の値段の総和以上であればTrueを返す条件が一番ノードを削除できるいい条件である.)
5種類の商品があり, それぞれの商品の値段が全て100円である場合を考える.1番目の層ラベルに存在するノードが1枝を通って, 2番目の層ラベルに存在するノードが0枝を通って到達するノード$\alpha$において$\phi(\alpha)=100$であり, $\phi(\alpha_{0})=100$である. この時, 300 - $\phi(\alpha_{0})$ = 200であり, これは残りの4番目から5番目の商品の合計200以上なので $\textrm{T-prune}(\alpha,0,x_{2}).BDD$=Trueである.(もし300-$\phi(\alpha_{b})$がそれ以降の商品の価値の総和+1円より大きいという条件なら枝刈りできてない!!) また, $\alpha$までの経路が示す集合は{{1}}, 4番目の商品から5番目の商品のべき集合は{{∅},{4},{5},{5,4}}であり, この集合和は{{1},{1,4},{1,5},{1,4,5}}である. ここから, 1番目の商品を選択し, 2,3番目の商品を選択しなかった場合の残りのあり得る集合は{{1},{1,4},{1,5},{1,4,5}}であることが探索をせずともわかった.
「300円問題」で例を示す.$\textrm{T-prune}(\alpha,b,x_{i}).ZDD$がTrueを返す時, $\alpha$のb枝の終点をTrueに接続し」かつ「根ノードから$\alpha$のb枝までの経路が示す集合がTrueとなる」 ような$\textrm{T-prune}(\alpha,b,x_{i}).ZDD$は, 300-$\phi(\alpha_{b})$がそれ以降のi+1の商品の値段のうち最小の値段の商品より小さければTrue, そうでなければFalseを返すような関数とすればよい.(これも, 例えば300-$\phi(\alpha_{b})$がそれ以降の商品の値段のうち最小の値段-1円より小さいという条件も$\textrm{T-prune}.ZDD$=Trueとなる条件となる. しかし300-$\phi(\alpha_{b})$がそれ以降の商品の値段のうち最小の値段より小さければTrueを返す条件が一番ノードを削除できるいい条件である.)
5種類の商品があり, それぞれの商品の値段が全て200円である場合を考える.1番目の層ラベルに存在するノード$\alpha$が1枝を通って到達するノード$\alpha_{1}$において$\phi(\alpha)=0$であり, $\phi(\alpha_{0})=200$である. この時, 300 - $\phi(\alpha_{1})$ = 100であり, これは残りのすべての商品の価格より小さいので $\textrm{T-prune}(\alpha,1,x_{1}).ZDD$=Trueである. また, $\alpha_{1}$までの経路が示す集合は{{1}}である. ここから, 1番目の商品を選択するとそれ以降の要素を含まない集合{{1}}が取りうる全ての集合であることが探索をせずともわかった.
トップダウン法アルゴリズム
n個の要素を持つ集合のべき集合のある条件を満たす部分集合を求めるためのトップダウン法は以下のようなアルゴリズムで進行する.
これを用いて, 今所持金Wを持っているときの購入することができる商品の組み合わせを求めるコードはgithubのknapsak.cppであり, 入力テキストはinput.knapsak.mdである.
ここで得られた決定図とそれによって得られる集合は以下の図のようである.
この上の図では6つのノードのみで求めたい集合族を表現しているが, 本来,決定二分木で表現するなら 1+2+4+16+32=55個のノードが必要になるということからもいかにコンパクトに集合を表現できているかがわかる.
枝刈りの意義
枝刈りの意義を再確認すると,一言で「無駄な探索を減らす」という点であった. 逆を返せば枝刈りをせずにも決定図を構築することは可能である. ためしに枝刈り部分を排除して先ほどの問題を解くと以下のような決定図が生成される.
これも同様に先ほどと同じ集合族を示す. しかし2つのグラフを見てもらうと上の図の方が圧倒的にコンパクトであることが見て取れる. 枝刈りは大事.(TD-DDはトップダウン(Top-Down)で作る決定図(Decision-Diagrams)の略)
マインスイーパー
マインスイーパーというゲームを御存じだろうか？
まずは以下の図を見てほしい.
(引用元はhttps://www.konangame.jp/mines_ai/minesweeper-how-to-ja/#google_vignette)
マインスイーパーのルール
以下,"https://mayonez.jp/topic/1030623#num_3978376" からの引用
マインスイーパーのゲーム画面は正方形のマスが敷き詰められていて,爆弾の置かれているマスを開けると爆発してゲームオーバーになります.
爆弾の置かれていないマスを開けたとき,隣接する8マスのどこかに爆弾がある場合はその個数が数字で表示され,隣接するマスに爆弾が置かれていないときは,それらのマスも同時に自動的に開けられます.爆弾を避けて爆弾の置かれていないマスをすべて開けられればクリアとなります.
つまりマインスイーパーのルールを簡単に言えば,押したら出て来る数字がヒントで,爆弾の場所を特定しながら爆発させずにセーフのマスだけを開けていくというゲームです.
目標
あるマインスイーパー盤面における閉じられた各マスにおいて爆弾が存在する確率を求めることで,各場面で閉じられたマスのうち最も爆弾存在確率が低いマスを開くことができる. つまり各場面で最適な選択をすることができるようになる.
手法
まずマスそれぞれを1つの頂点としてみる. ヒント1以上の開いているマスをそれぞれ$u_{1},u_{2},....,$,ヒント1以上の開いているマスの周辺に存在する閉じているマスを$v_{1},v_{2},....,v_{n}$とし, 開いてる頂点の集合を$U$, 閉じているマスの集合をVとする.開いているマスと閉じているマスを辺で接続させるとこのグラフは2部グラフとなることがわかる.(以下このグラフをGとする) 下はそれを示した図
図2
(引用はhttps://eprints.lib.hokudai.ac.jp/dspace/bitstream/2115/74087/1/Hirofumi_Suzuki.pdf)
Vのうち爆弾がありうる組み合わせ集合, つまりありうるマインスイーパーの爆弾の配置を全て列挙すしたい. そしてこれはこのグラフの任意の$v$に対して次数制約をみたす全ての部分グラフを求める問題と見ることができる.
ここで, ある頂点$v$が満たすべき次数制約を「ある頂点$v$の次数が集合dc(v)の要素の1つである」こととする.
定義より, 任意の開いた頂点$u$の次数制約は$dc(u)$=($u$のヒント)である. ここで, 閉じた頂点$v$が爆弾であったらその頂点は今周辺に存在する全て開いている頂点と接続する. 爆弾でないなら周辺にあるどの頂点とも接続しない. Gの各頂点vにおいて次数を$deg_{G}(v)$とすると, $dc(v)$={$deg_{G}(v) or 0$}である.
全探索すると
この問題を全探索で解く, つまり閉じたマスのべき集合を考え, それが次数制約を満たすかどうかを考える方法は, $2^{|V|}$だけ考えなければならない状態があり, |V|が大きくなると爆発的に大きくなる. よって, トップダウン法を用いた決定図で求めていく.
トップダウン法でやる
トップダウン法における「ある集合が解の要素になるか」のconfiguration部分は次数制約条件である. そして要素の部分をグラフG辺集合Eとする. 頂点集合から辺集合を考えるようになったのは, 辺集合が求まればその誘導グラフが作成でき, 自然と頂点集合が求まるからである. 今回は下のような13個の辺を持つグラフについて考えよう.
図1
(引用はhttps://eprints.lib.hokudai.ac.jp/dspace/bitstream/2115/74087/1/Hirofumi_Suzuki.pdf)
configuration
さて, この問題のある集合が解の要素になるか」の部分が次数制約条件であるため, configurationは各$v$の次数と考えることができ, そのため$\phi$は配列$\phi$ = [$\phi_{v_{1}},\phi_{v_{2}},....,\phi_{v_{n}}$] ($\phi_{v}$は$v$の次数)と定義できる.
ノード生成
層ラベルiに存在するノード$\alpha$の0枝と1枝の終点$\alpha_{0}$と$\alpha_{1}$の$\phi(\alpha_{0})$,$\phi(\alpha_{1})$は$\phi(\alpha_{0})$=$\phi(\alpha)$,i番目の辺に接続する両端の頂点$v1,v2$に対して$\phi_{v1}(\alpha_{1})$=$\phi_{v1}(\alpha) + 1$,$\phi_{v2}(\alpha_{1})$=$\phi_{v2}(\alpha) + 1$と遷移できる. というのもi番目の辺を選択したなら両端の次数は+1され, 選択しなかったら次数の変化はないからである.
False枝刈り
層ラベルiに存在するノード$\alpha$がb(b=0or1)枝を通ったとする. i番目の両端の頂点を$v_{1}$,$v_{2}$とし, i+1番目以降の辺を全て加えた際に$v_{1}$,$v_{2}$の増える次数を$j_{1}$,$j_{2}$とするとFalse枝刈りができるのは「$\phi_{v_{1}}と\phi_{v_{1}}+j_{1}$の間に$dc(v_{1})$の要素が含まれていない」または「$\phi_{v_{2}}と\phi_{v_{2}}+j_{2}$の間に$dc(v_{2})$の要素が含まれていない」時である. これは上の条件が満たされるとき,層ラベルiに存在するノード$\alpha$がb枝を通った時点でそれ以降の辺をどう選んでも次数制約を満たさない頂点が少なくとも1つ存在するからである.
True枝刈り
True枝刈りは, $n$番目の層がb枝(b=0or1)を通った時点で発動する. 実をいうと, ノードを削減できる意義のあるTrue枝刈りは見つかっておらず, それゆえn番目までの選択でFalseとさせなかった集合をTrueとする(中身のない)True枝刈りしかできない.(このTrue枝刈りはZDDともBDDともとらえることができる)
これらの理論を一般に実装したのがgithubのDCS.cppであり,入力テキストはinput.DCS.mdである.
そして, このプログラムで図1をトップダウンに決定図を作成すると以下のようになる.(Fへ向かう枝は今回無視してる,入力テキストはgithubのgitgraph1.txt)
上のようにマインスイーパーの爆弾配置の全ての配置(今回は6個の配置)を列挙することができた.
そして, これをもとに各閉じたマスに対して爆弾が存在する確率を計算することができ, その導出は各$v$に対する爆弾がある存在確率を$p(v)$とすると
p(v)=(vを含む組み合わせの数)/(ありうる組み合わせの数)である.
これをもとに$v_{1}$から$v_{5}$までの爆弾が存在する確率は,
\displaylines{
p(v_{1})=\frac{3}{6} = \frac{1}{2} , p(v_{2})=\frac{4}{6} = \frac{2}{3}
,p(v_{3})=\frac{3}{6} = \frac{1}{2}
\\
p(v_{4})=\frac{4}{6} = \frac{2}{3}
,p(v_{5})=\frac{4}{6} = \frac{2}{3}
\\
}
ここから, 次に開けるマスとして爆弾がある確率が低い$v_{1},v_{3}$を選択することが最善の選択しであると考えられる. また, 二分決定木に必要なノード数が$\sum_{1\le k\le 13}2^{k-1}$=8191個であるのに対して, 今回56個のノードしか使ってない. いかにコンパクトに情報がまとめられているかが見て取れるだろう.
同じ考え,つまり決定図を作り全ての組み合わせを作ったうえでで上で既出したマインスイーパーの閉じている各マスの爆弾存在確率を求めるとそれは以下の図のように確認することができる.(入力テキストはgithubのgraph2.txt)
以上の結果により,図1,2状況下のマインスイーパーで最善手を打つことができる.
扱う辺が多くなった時の対策
いま扱った2つのグラフは辺が少なく扱いやすい形であり, 決定図を用いたアルゴリズムのプログラミングを使わなくても自力解ける程度の問題であった. ということでプログラムを改良しつつ自力で解くことが難しいとされている問題を扱っていこう.
図3
以下はネットから拾ってきた問題である. 赤い旗は閉じてるマスの内爆弾存在確率が100％のマスとすぐわかるマスを表示してくれている(優しい).閉じているマスでのうち爆弾存在確率が0であるマスをできるだけ求めたいらしい. 読者は何個マスが見つかっただろうか？(ちなみに自分は1つもわからなかった)
ということでこの図を2部グラフに直し, トップダウンに決定図を作成していこうとした.しかしこのグラフは46の辺から構成されるため, 作るのは46の層から成る決定図であり, これまでのプログラムを動かすと非終端のノードは260個(ちなみに二分決定木でのノード数は約70兆なのでこれでも非常に非常に非常にコンパクト)あるためこの図を作成して組み合わせを求めて, 各辺について存在確率を求める..というのは非常に面倒くさいので自動でその操作をおこなえるプログラムも追加していった. (DCS.cppは初めからそのコーディングを済ましてある)
これにより, 各頂点に対して存在確率を次のターミナルが示すように導出できる.(入力はgithubのgraph3.txtによる)
これを図に直すと以下のようである.
ということで複雑な状況においても同じアルゴリズムを用いて全ての閉じているマスの爆弾存在確率が導出できた.
付録.共有条件,枝刈りが与えるスピート効果
共有条件はその後同じ経路をたどる2つのノードを1つにすることで,枝刈りは探索を途中で終了することで必要な情報を軽減する, と述べたがこれがどれほどの効果をもたらすのだろうか? いままで取り上げた最初の2つのマインスイーパーと辺の数|E|=3,5,8,11における以下のマインスイーパーの盤面を用意して比較していく. 比較方法は共有条件, 枝刈りに相当するノードをそれぞれコメントアウトするとともにclock関数を用いて時間を測定するだけである.(E=13,E=16はそれぞれ本文に記載した1,2番目のマインスイーパーの盤面である)(E=3,5,8,11における入力テキストはgithubにおけるE=3.txt,E=5.txt,E=8.txt,E=11.txtである).
結論として, 以下の図とグラフを得ることができた(途中経過を示すのは割愛する)
左側に決定図のノードの数を記載し, 右側にかかった時間(n秒かかったらnsと表記)を記載した.
これをグラフにプロットすると以下のようである.(作成はgnuplotを用いた)
グラフ1.横:ノード数,縦:(決定図で用いるノード数/二分決定木で用いるノード数)の関係
report both.txt:枝刈り＋ノード共有どちらもした場合
report only co.txt:ノード共有のみした場合
report only pr.txt:枝刈りのみした場合
グラフ2.横:ノード数,縦:必要時間の関係(1)
report2 nothing.txt:枝刈り,ノード共有どちらもしなかった場合
report2 only co.txt:ノード共有のみした場合
グラフ3.横:ノード数,縦:必要時間の関係(2)
report2 both.txt:枝刈り,ノード共有どちらもした場合
report2 only pr.txt:枝刈りのみした場合
図及びグラフから以下のことが読み取れる.
・ノード共有及び枝刈り操作で削除できるノード数と枝刈り操作のみで削除できるノードの数は等しいので, ノード共有及び枝刈り操作においてノード共有操作は仕事をしていない.(理由がわからないのでわかる人教えてください)
・一方,ノード共有操作のみにおいては共有操作を起こす.
・ノード共有操作および枝刈り操作いずれもノード数が10000を超えると削除できるノード数の割合がほぼ一定になる.
・ノード数が大きくなって増加率が一定になるとノード数とかかる時間は比例するようになることが見て取れる. これは操作に必要な時間がノード数に比例するアルゴリズムからも合点がいく.
・ノードの削除率の違いから枝刈り,共有条件両方の操作と枝刈り操作の場合に対する必要時間はおおまかに対数関数を描くのに対して, 共有操作のみの操作なにもしない場合の操作に対する必要時間は直線を描く.
興味のある人へ
今回紹介した決定図は集合表現やグラフ理論において幅広く応用されているがそれの端緒となったのがs-t経路問題といわれている(らしい).
そのs-t経路問題をわかりやすく問題提起した動画がyoutubeに存在するので良ければ見て, もっと良ければその解決策をZDDやトップダウン法で考えてみてくれると面白いかもしれない.
https://www.youtube.com/watch?v=Q4gTV4r0zRs
あとがき
今回は決定図によりコンパクトに情報を処理する方法について考察してみました.
今回参考にした論文と書籍は湊先生かその研究室の著作の物が多く偶然にも先生は自分が在籍してる学科にいらっしゃるのでいつか話に行きたいです.
指導をしてくれた小島先生ありがとうございました.
主な参考資料
https://eprints.lib.hokudai.ac.jp/dspace/bitstream/2115/74087/1/Hirofumi_Suzuki.pdf
https://www.ai-gakkai.or.jp/jsai2016/webprogram/2016/pdf/927.pdf
https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%B1%BA%E5%AE%9A%E5%9B%B3
https://qiita.com/kpasso1015/items/802885926c41cc8d3132
超高速グラフ列挙アルゴリズム (著：湊真一)