８パズル解読

８パズル解読

３×３の盤があり、盤上には１～８の番号のついた駒と空所（丸の場所）があります。空所には上下左右の駒を滑らせて移動させることができる。
上図の初期状態から下図で示す最終状態へ戻す手順を、横型探索で求めた場合とＡ*アルゴリズムで求めた場合を比較検討するとどうなりますか？？

　―――――――――
　|　2　|　8　|　3　|　
　―――――――――
　|　1　|　6　|　4　|
　―――――――――
　|　7　|　○　|　5 |
　―――――――――

↓

　―――――――――
　| 1 | 2 | 3 |　
　―――――――――
　| 8 | ○ | 4 |
　―――――――――
　| 7 | 6 | 5 |
　―――――――――


よろしくお願いします　

No.1 ベストアンサー 回答者： payForward 回答日時： 2007/07/10 01:17

こちらは、数学というよりプログラムの課題でしょうか？

それとも、どういう結果が出るかということのみ示せばいいでしょうか？

結果をいえば、横型探索、A*アルゴリズムどちらを用いても、最小の手数で並び変える手順を見つけることができるはずです。
しかし、（プログラムの実装能力にもよりますが）横幅探索の方が時間がかかってしまいます。

横型探索というのは、どういうものかはわかりますでしょうか。
まず、一回動かした場合の盤面について全部記憶します。
次に一回動かしたところから、さらに一回動かした盤面をすべて記憶します。
このとき、以前に覚えた盤面である場合は、記憶しません。

このようにして、一回動かしたすべての盤面を計算。
その中に答えの盤面がなければ２回動かしたすべての盤面を計算、
その中に答えがなければ・・・・
というのを繰り返すことになります。
そのため、一番少ない回数で動かした答えまでの手順を見つけることができますが、時間がかかってしまいます。


時間をかからなくする工夫がA*アルゴリズムです。
これは、その盤面から「最低でもあと何回動かさないと答えの盤面にならない」という情報を利用するものです。
たとえば、１～８のそれぞれのパネルについて、正しい位置までの距離がどれくらいあるか（たとえば１が右下にあれば距離は４）を計算し、合計したものが、「あと最低何回動かさないといけないか」という情報として利用できます。（なぜかは考えてみてください）
A*はこの情報を用いて、一番最小の手数となる手順を探していきます。
たとえば、
３回動かした盤面があり、そこからあと「最低でも６回」動かさないといけない
とすると、
この盤面を通って答えにたどり着くのはトータルで最低９回かかる
ということになります。
このトータルで最低何回かかるか、というのを比べ、見積もりが小さい盤面から順に探索していくのがA*アルゴリズムとなります。

どういった答えが求められてるのか自信がなかったので、
とりあえず説明してみましたが・・・