A*探索アルゴリズム

[Nな人]

お初にお目にかかります。
アルゴリズムのことで質問をさせていただける場所を探していると、
こちらが良いと教えていただいたのでスレッドを建てさせていただきました。

今回、迷路を自動で解くプログラムを作成しているのですが、
その際に最短ルートを求めたいと思い、いろいろ調べていると、
A*探索アルゴリズムというものを見つけ、それを使ってみようと思っているのですが、
難しくなかなか理解ができません。

様々なサイト様をめぐって、
「スタート地点から自分が今いる地点の距離と、自分が今いる地点からゴール地点までの距離を足しあわせて考えていく」
ということは分かりましたが（違うかもしれませんが……）、どういう流れで作成して行けばいいのか
さっぱりとわかりません。

C言語の知識は浅いですが、独学でBASICをかじっています。
（ギリギリポインタがわかりはじめた感じですが）

いきなりで不躾だとは思いますが、
プログラムの流れや詳しい考え方など、ご存じの方がいらっしゃいましたらご教授いただけませんでしょうか。
よろしくお願いいたします。

[softya（ソフト屋)]

イメージ的なモノは、これが分りやすいかも知れません。
「経路探索アルゴリズムの「ダイクストラ法」と「A*」をビジュアライズしてみた - てっく煮ブログ」
http://d.hatena.ne.jp/nitoyon/20100126/ ... _visualize

ここが参考に成るでしょう。A*のベースとなったダイクストラ法です。
「グラフ構造を用いた経路探索（ダイクストラ法）」
http://tokyo-ct.net/usr/kosaka/for_stud ... ugi26.html
あとＣ＃のサンプルコードです。
「Ａ＊（エースター：最短経路探索アルゴリズム）サンプル」
http://tkina.web.fc2.com/kaihatu/siryou ... Sample.htm
「ゲーム制作の舞台裏 エースターで最短経路探索」
http://tkina.blog60.fc2.com/blog-entry-326.html

コードではないですが
「A*」
http://www5f.biglobe.ne.jp/~kenmo/progr ... astar.html

[Nな人]

softya（ソフト屋)　様

ご返信ありがとうございました。
完成はしませんでしたが、とても参考になりました！！
もっとゆっくり時間をかけて完成させて行こうと思います。

[GRAM]

A*アルゴリズムとはダイクストラ法と呼ばれる探索アルゴリズムの改良なので
まずはダイクストラ法を理解することが大切です。
（というかダイクストラさえ分かればA*に変えるのは簡単です）

ダイクストラ法に関する説明は上記サイト（特に2番目）にある通りですので、
プログラムにするときに自分が考えることを挙げておきます。

まず、ダイクストラ法ですが僕が思うに次の3つの機構からなります。
どの言語を使うにしろ、この3つの機構が作れればできたも同然です。

①そこに行きつくまで合計コストが最小となる次の探索ノードを取り出す機構（プライオリティーキュー）
②取り出したノードがゴールかどうか判定し、またそこから伸びる各ノードへのコストを計算する機構
③最小コストの確定したノードを保存する機構（最短経路ツリー）

今各ノードは探索用に以下の3つの情報を持っているとしましょう。
①そのノードまでのコスト
②そのノードにたどり着く一つ前のノード
③そのノードから伸びる各ノードと自分のノードから各ノードに行くまでにかかるコスト


まず初めにプライオリティーキューにスタートとなるノードを加えます。
（ループはじめ）
①プライオリティーキューから一番コストの低いノードを取り出します。
　　プライオリティーキューから取り出されるノードは、プライオリティーキューの性質上
　　コストが確定されているノードです。（つまりコストが最も低い）
②そこで取り出したノード（ノードＡとする）を最短経路ツリーに加えます。この時始めのノードの場合のみ一つ前のノードは記録されていません。
③ノードＡがゴールならループを抜けます
④ノードＡから伸びるノード（ノードＢとする）へノードＡからかかるコストを取得します。最短経路ツリーにノードＢが入っていれば何もしません。
　　そうでなければ、ノードＡのコストと和をとってノードＢのコストを算出します。
　　プライオリティーキューにノードＢが入っていなければ、ノードＢのひとつ前のノードをノードＡに設定しプライオリティーキューに加えます。
　　プライオリティーキューにノードＢがすでに入っていて、かつ今算出したコストのほうが低ければ、ノードＢのコストを更新して、
　　ノードＢのひとつ前のノードを、ノードＡに設定し記録します。実装によってはプライオリティーキューを更新します。
⑤④をノードＡから伸びるすべてのノードについて行います
⑥（ループはじめ）に戻ります。

これで終わりです。
最短経路ツリーにはゴールまでの最短経路が記載されます。
というのも各ノードのひとつ前のノードが何かわかっているので、ゴールから順に初めのノードに向かってめぐっていけば、
勝手に最短経路が出来上がります。
実装が一番難しいのはプライオリティーキューですが、効率を考えなければそこまでではありません。
頑張ってください！