A*アルゴリズムで８パズル解いてみた - 似非学問的な手記
まず、「A*アルゴリズム（A*探索アルゴリズム）」というのは、ダイクストラ法を改良したようなものです。 ダイクストラ法というのは、初期状態からノードまでの必要最小コストが小さいものから順に探索していく方法で、具体的には (0)まず、最初にリストに初期状態を入れる (1)リストから、「初期状態からの必要最小コスト」の値が最も小さいノードを選ぶ。 (2)そのノードから到達できる状態を調べ、リストに追加する。 (3)目的の状態に到達したら終わる。 (4)到達しなかったら(1)から繰り返し。とまあそんな感じですな。 「必要最小コスト＝初期ノードからの移動回数」なら幅優先探索と同じになるわけです。 次に、「Aアルゴリズム」とは、ここに「たぶんあとこれぐらいで目的の状態に着く」という、 目的地までのコストの推定値を求める関数（ヒューリスティック関数）h*(x)(xはノード)を考えて、 さっきのアルゴリ
アルゴリズム講座/実践編/ハッシュ法(幅優先探索)
思考アルゴリズムの王様バックトラックにも弱点があります。その弱点と克服法を考えてみます。ちょっと難しくなりますが「再帰」は使用しないので、ある意味ではむしろ人に分かり易いアルゴリズムなのかも知れません。 １．「１５パズル」のミニ版「５パズル」を解く 右図の５枚のパネルをランダムにシャッフル後、パネルを上下左右に スライドして元の順番通りになる様に最小の手順で並べ直して下さい。 この問題に先ほどのバックトラックを使っても失敗します。何故なら 「堂々巡り」という現象が発生してしまうからです。 堂々巡りとは、局面Ａから局面Ｂへと変化しさらに局面Ｃへと探索が 進んでいったが、もしいつしか元の局面Ａに変化してしまったらこれま での探索の過程が繰り返し実行されてしまいます。これでは無限地獄。 これを防止するには、探索過程の総ての局面を保存しておいて過去に 同じ局面がなかったかをチェックしながら探索しな
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
15パズル自動解答プログラムの作り方
