A*(A-star)を利用して(非効率に)9パズルを解いてみた。

9パズルとは?

　9パズルとは縦に3枚、横に3枚、合計9枚のパネルが入る正方形の枠に、1から9までの数字が書かれた8枚のパネルが埋め込まれたパズルです。つまり枠内には一枚分の空白があり、その空白に隣り合ったパネルをスライドさせながら、ばらけていた数字を指定通り完成させることが目的となります。

　――と書いてみても、さっぱりわかりづらいので、とりわけ説明が充実していたニコニコ大百科のページをリンクしておきます。

　上記記事は15パズルに関するものですが、9パズルはそれが小さくなっただけで、ほとんど同じです。

　さて今日はこの9パズルをA*(A-star)と呼ばれるアルゴリズムを利用して、答えに至る最短手順を計算したいと思います。

A*(A-star)とは?

　A*(A-star)は経路探索アルゴリズムのひとつです。特徴としては2点。まずは最短距離が求められるという点。もちろん条件付きではあるのですが、その条件については後回し。次の特徴としては評価関数を利用する点。評価関数が小さい値をかえすノードを優先的に探索していきます。

　さてその評価関数fですが、とある局面をnとすると、次のように表現できます。

f(n) = (スタートからnに至るまでのコスト) + (nからゴールに至るまでのコスト)

　では局面をn、前者をg(n)、後者をh(n)とすると、g(n)に関しては簡単にもとめることができるのですが、問題はh(n)。探索途中だとゴールまでの手順が未確定なため、h(n)に関しはっきりしたことが言えないのです。そこでA*においてはこれを別の推測値h'(n)によって代替します。そしてこのh'をヒューリティクス関数といいます。

　ただし、h'についてはh'(n) < h(n)を満たす必要があります。つまりゴールまでの推測コストは実際のコストを超えないよう計算せねばなりません。

　以上をふまえたうえで実際の手順を確認してみましょう――といきたいところですが、ここでわたしがうだうだ書くよりwikipediaの当該記事を見ていただく方が簡潔でわかりやすいと思います。一応その部分だけは引用しておきますが。

1. ゴールノード（G ）とスタートノード（S ）を作成する。また計算中のノードを格納しておくためのリスト（Openリスト）と、計算済みのノードを格納しておくリスト（Closeリスト）を用意する。
2. スタートノードをOpenリストに追加する、このとき g(S) = 0 であり f(S) = h*(S) となる。また Closeリストは空にする。
3. Openリストが空なら探索は失敗とする（スタートからゴールにたどり着くような経路が存在しなかったことになる）。
4. Openリストに格納されているノードの内、最小の f*(n) を持つノード n を取り出す。
5. n = G であるなら探索を終了する。それ以外の場合は n を Close リストに移す。
6. n に隣接している全てのノード（ここでは隣接ノードを m とおく）に対して以下の操作を行う
   1. f '(m) = g(n) + h(m) + COST(n,m) を計算する、ここで COST(n,m) はノード n から m へ移動するときのコストである。また g(n) は g(n) = f(n) - h(n) で求めることができる。
   2. m の状態に応じて以下の操作を行う
      • m が Openリストにも Closeリストにも含まれていない場合 f*(m) = f '(m) とし m を Openリストに追加する。このとき m の親を n として記録する。
      • m が Openリストにある場合、f '(m) < f(m) であるなら f(m) = f '(m) に置き換える。このとき記録してある m の親を n に置き換える。
      • m が Closeリストにある場合、f '(m) < f(m) であるなら f(m) = f '(m) として m を Openリストに移動する。また記録してある m の親を n に置き換える。
7. 3 以降を繰り返す。
8. 探索終了後 G から親を順次たどっていくと S から G までの最短経路が得られる。

いざ実装!

　前置きが長くなりましたが、実際にコーディングしていきましょう。

　実行時間は0.1秒程度。よしよし。成功しているようですね。まあwikipedia通り実装しただけですが。

　今回引っかかったのは2点。まずヒューリティクス関数h'をどうするかについて。今回はマンハッタン距離と間違った場所におかれているパネルの枚数の合計値を利用しましたが、もっと良いものがあったように思います。

　次に同じオブジェクトが等しいかどうかの判定。新しくこちらで用意したクラスには当然新しく==を定義する必要があるということです。これに気づかずずいぶん苦労しました。というかコーディングで悩んでいた時間のほとんどがこいつのせい。

実は……

　さてここまで完璧にできたかのように書いていますが……

　実のところ重大な欠点があります。

　上の例では10手程度で完成するパズルを解かせているため、実行時間は0.1秒で済んでいますが、これがたとえば30手などになると、同じ実行環境でも60秒ぐらい平気でかかります。上で引用したニコニコ大百科の記事曰く、15パズルなどになると最短手順が80手になる場合すらあるそう。わたしの作ったプログラムでは解くのにいったいどれだけかかるやら……

　要するにわたしの書いたコードは「重い」ということです。そもそもA*自体、それほど「軽い」アルゴリズムではないようですが、わたしの場合はちょっと異常。そこで一応その理由を考えてみると……

1. Rubyらしいコードやクラス設計を心掛けたため、あっちこっちでオブジェクトを生成しており、これに時間が取られている。
2. とくにStateオブジェクトはふたつのPazleオブジェクトが必要なうえ、これを何千個と保持するため、メモリを圧迫している。
3. Rubyにはプライオリティキューがないため、openリストをいちいちソートせねばならない。

　上2つに関しては全体の設計を見直すことにより改善しそうですが、3番目はRuby自体の問題(?)でどうしようもありません。

　データ構造やアルゴリズムの勉強をしていると、どうしてもプライオリティキューがほしくなりますね。gemを探せばあるのでしょうが、やっぱり標準添付ライブラリで何とかしたいと思う今日この頃です。