それなりブログ

とあるWebエンジニアのそれなりのブログ、JavaScript/Node.js/Python/PHP/ゲーム作成 など

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

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

参考リンク

ダイクストラ法と比較しての個人的な理解

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

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

追記:

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

(ありがとうございま)シタッ > @mizchi


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


コメントを残す

メールアドレスが公開されることはありません。

Categories

Archives