組み合わせ爆発の問題を解こう その7 – A*アルゴリズムで解く
2012-09-28Mathematics
では、A*を使ってスライドパズルを解いてみたいと思います。図で示そうと思いますが、いくら計算量が少ないA*といえども、解いているうちに、どんどん図が大きくなっていくので、A*の動きがわかるくらいの図まで、用意いたしました。
図中のスライドパズルの状態については、次のような意味を持っています。
右半分、上段のPathの長さがg*(n)の値に、完成状態と比べた時のずれ具合がh*(n)の値に相当し、その2つの値を足したものがf*(n)の値に当たります。
では、スタートの状態からすすめることにします。
A*アルゴリズムを使う場合には、計算中の枠と、計算済みの枠を用意します。まず初めに、計算中の枠に、スタートの状態のスライドパズルを入れます。
次に、計算中の枠内のスライドパズルから、f*(n)の値が最も小さいものを1つ選び、空マスを動かせる方向に動かします。この時、動かした後の状態がすでに計算済みにある場合は、その動かし方は無視します。
計算中の枠から取り出したスライドパズルを計算済みに移し、新しく作ったスライドパズルの状態を計算中に入れます。
今度はまた、計算中の枠から、f*(n)の値が最も小さいものを1つ選び、空マスを動かします。
先ほどと同じように、計算中の枠から取り出したものを計算済みに、新しく作った状態を計算中に入れます。
これをどんどん繰り返すのです。上図では、次に計算中の枠から、f*(n)の値が小さいものを取り出すことになりますが、f*(n)の最小値である7を持つ状態が2つあるので、どちらかから先に取り出すことになります。同じf*(n)の値を持つものが、複数計算中の枠内にあることはいくらでもあるので、その場合は適当に選ぶしかありません。
さて、こうすれば、ゴール状態に近いものから動かし方の可能性が吟味できるので、効率的ですね。
これを、次の条件になるまで繰り返します。
- 計算中の枠から取り出して、空マスを移動させたときに完成状態になったとき。この場合は、解答が見つかったということなので、これまでのPathと現在動かした方向を繋いだものを、動かし方の解答として出力すれば良い。
- 計算中の枠内の要素が0になった時。この場合は、有効な動かし方が見つからなかったということである。
スライドパズルを解くために、A*アルゴリズムを若干改変して使いました。正しいA*アルゴリズムについては、WikipediaのA*の項目を参照して下さい。
一応これでもある程度の大きさのスライドパズルなら数秒～数分で解くことができますが、それでも解けない場合があります。その場合は、例えばスライドパズルを部分に分割して部分ごとに解く、とか、別の方法を考える必要がありそうです。
ということで、だいぶ長くなりましたが、次回はまとめで、組合せ爆発の記事を終わらせたいと思います。
Topic
- Mathematics (15)
- Natural Language Processing (1)