- ベストアンサー
８パズル解読とは？横型探索とＡ*アルゴリズムの比較検討
- ８パズル解読は３×３の盤上で行われるパズルで、番号がついた駒を移動させて最終状態へ戻す手順を求めるものです。
- 横型探索とは、幅優先探索を用いて全ての可能な手順を調べる方法です。
- Ａ*アルゴリズムは、最短経路を求めるための探索アルゴリズムで、ヒューリスティック関数を使用して最適な手順を見つけることができます。
- みんなの回答 （1）
- 専門家の回答
質問者が選んだベストアンサー
こちらは、数学というよりプログラムの課題でしょうか？ それとも、どういう結果が出るかということのみ示せばいいでしょうか？ 結果をいえば、横型探索、A*アルゴリズムどちらを用いても、最小の手数で並び変える手順を見つけることができるはずです。 しかし、（プログラムの実装能力にもよりますが）横幅探索の方が時間がかかってしまいます。 横型探索というのは、どういうものかはわかりますでしょうか。 まず、一回動かした場合の盤面について全部記憶します。 次に一回動かしたところから、さらに一回動かした盤面をすべて記憶します。 このとき、以前に覚えた盤面である場合は、記憶しません。 このようにして、一回動かしたすべての盤面を計算。 その中に答えの盤面がなければ２回動かしたすべての盤面を計算、 その中に答えがなければ・・・・ というのを繰り返すことになります。 そのため、一番少ない回数で動かした答えまでの手順を見つけることができますが、時間がかかってしまいます。 時間をかからなくする工夫がA*アルゴリズムです。 これは、その盤面から「最低でもあと何回動かさないと答えの盤面にならない」という情報を利用するものです。 たとえば、１～８のそれぞれのパネルについて、正しい位置までの距離がどれくらいあるか（たとえば１が右下にあれば距離は４）を計算し、合計したものが、「あと最低何回動かさないといけないか」という情報として利用できます。（なぜかは考えてみてください） A*はこの情報を用いて、一番最小の手数となる手順を探していきます。 たとえば、 ３回動かした盤面があり、そこからあと「最低でも６回」動かさないといけない とすると、 この盤面を通って答えにたどり着くのはトータルで最低９回かかる ということになります。 このトータルで最低何回かかるか、というのを比べ、見積もりが小さい盤面から順に探索していくのがA*アルゴリズムとなります。 どういった答えが求められてるのか自信がなかったので、 とりあえず説明してみましたが・・・
