【えーすたーあるごりずむ】
A*アルゴリズム とは？
💡 「たぶんあっちが近い」という勘を活かして、賢くゴールを目指す探索の優等生
📌 このページのポイント
ひよこ A*ってダイクストラ法と何が違うの？
ペンギン先生 ダイクストラ法は「出発地からの距離が近い順」に探索するけど、A*は「出発地からの距離＋ゴールまでの推定距離」が小さい順に探索するんだ。つまり「ゴールの方向にありそうなルート」を優先的に調べるから、無駄な探索が減るんだよ
ひよこ 「推定距離」ってどうやって計算するの？
ペンギン先生 ヒューリスティック関数と呼ばれるもので推定するよ。たとえば2次元の地図なら、現在地からゴールまでの直線距離を使うのが定番だね。実際の道のりは直線より長いから、「少なくともこれだけはかかる」という下限値になるんだ
ひよこ ゲームのキャラクターが障害物を避けて歩くのもA*？
ペンギン先生 まさにそう！RPGやリアルタイムストラテジーで敵キャラが壁を避けてプレイヤーに向かってくるのは、裏でA*が動いていることが多いよ。グリッドマップ上で障害物を避けつつ最短ルートを見つけるのが得意なんだ
ひよこ ダイクストラ法より絶対いいの？
ペンギン先生 ゴールが決まっている場合はA*の方が高速だけど、ヒューリスティック関数の選び方が重要なんだ。推定値が実際より大きすぎると最短経路を見逃すことがある。逆にヒューリスティックを0にするとダイクストラ法と同じ動きになるよ。道具は使い分けが大事だね
📖 おまけ：英語の意味
「A-star Algorithm」 ＝ A*（エースター）アルゴリズム
💬 1968年にピーター・ハート、ニルス・ニルソン、バートラム・ラファエルが発表したよ。「A」はアルゴリズムの改良版を順にA1、A2…と名付けていた中で「最良」を意味する「*（スター）」を付けたんだよ