A* (A-star, エースター) 探索アルゴリズムのメモ

個人開発を支える技術Night の雑談にて、ダイクストラ法よりも効率が良い経路探索アルゴリズムの話を聞いたのでメモっとく。

以下、上から順に観る/読むと良い：

A* Pathfinding Algorithm Visualization (動画)

A*（A-star：エースター）探索アルゴリズムの原理

Algorithms with Python – ヒューリスティック探索 (A*箇所から読んで良い)

ダイクストラ法は、ゴールを確認せずに、「そのノードまでの移動コスト」が少ない順にノードを展開する。

A*は、「そのノードまでの移動コスト ＋ ゴールまでの推定移動コスト」で、次に展開するノードの優先順位を決める。
「ゴールまでの推定移動コスト」は、直線距離だったり、マス目を1として数えたり、とか、「最短」である必要があるようだ。（正確には「最短」じゃなくてもいい、「h* <= h」であれば良いらしい？） これにより、正解の経路を引きやすくなる。 なお、FEのようにマス目の種類で移動コストが激しく変わったりすると、推定が上手く働かなくなって、あまり有効ではなくなると思われる。（※ 計算量が多くなるだけで、正しい経路は導き出せる） ・・・間違ってたら指摘して下さい！

参考にならない参考資料) 昔作った何法でもない経路探索ライブラリ

(ありがとうございま)ｼﾀｯ ＞ @mizchi