A*アルゴリズムで８パズル解いてみた - 似非学問的な手記
まず、「A*アルゴリズム（A*探索アルゴリズム）」というのは、ダイクストラ法を改良したようなものです。 ダイクストラ法というのは、初期状態からノードまでの必要最小コストが小さいものから順に探索していく方法で、具体的には (0)まず、最初にリストに初期状態を入れる (1)リストから、「初期状態からの必要最小コスト」の値が最も小さいノードを選ぶ。 (2)そのノードから到達できる状態を調べ、リストに追加する。 (3)目的の状態に到達したら終わる。 (4)到達しなかったら(1)から繰り返し。とまあそんな感じですな。 「必要最小コスト＝初期ノードからの移動回数」なら幅優先探索と同じになるわけです。 次に、「Aアルゴリズム」とは、ここに「たぶんあとこれぐらいで目的の状態に着く」という、 目的地までのコストの推定値を求める関数（ヒューリスティック関数）h*(x)(xはノード)を考えて、 さっきのアルゴリ
ALGORITHM NOTE 幅優先探索 Breadth First Search
幅優先探索はグラフにおける幅優先探索と同様に動作し（グラフのノードを状態とみなします）、幅広く状態変化を行います。つまり、現在の状態から可能な全ての状態変化を行い新しい状態を作ります。この探索をシステマティックに行うために、状態変化によってつくられた新しい状態をキューに追加し、探索を展開するためにキューの先頭の状態からさらに状態変化を繰り返します。一度生成した状態を再び作らないために、生成された状態を全て記録する必要があります。幅優先探索は、問題に解が存在すれば初期状態から最終状態までの最短の経路を求めます。 それでは、８パズルを幅優先探索で解いてみましょう。 プログラムの説明 以下のプログラムは、例えば 2 8 3 x 1 5 4 7 6 というような、'x' をスペースとみなしたパズルを読み込み、 ldruuldlu という、l = left, r = right, u = up, d
デジなか−なかよしゲーム
15パズルは、19世紀終わりごろに考え出されたパズルです。 みんなも解き方をおぼえて、 ぜひいろいろな15パズルを解いてみてね。
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
15パズル自動解答プログラムの作り方