A*（エースター）探索は、グラフ探索や最短経路問題を解くための代表的なアルゴリズムです。出発点から目標地点までの最小コストを推定する際、現在の実績コストに「ヒューリスティック関数」による推定残りコストを加算した「評価関数」を用います。これにより、ダイクストラ法よりも効率的に最適な経路を発見できます。
A*探索とは
A*探索は、スタート地点からゴール地点までの最短経路を効率的に見つけるためのグラフ探索アルゴリズムです。現在の地点に到達するまでにかかった実際のコストと、ゴールまでにかかると予想される推定コストを足し合わせた値を用いて、探索の優先順位を決定します。
詳しく解説
A*探索は、1968年に開発された歴史ある探索アルゴリズムであり、現在でもゲームAIやロボットの経路計画などで広く利用されています。このアルゴリズムの最大の特徴は、評価関数 f(n) = g(n) + h(n) を使用する点にあります。ここで g(n) はスタートから現在のノード n までの確定した実績コスト、h(n) は現在地からゴールまでの予測コストを表すヒューリスティック関数です。この予測に適切な関数（直線距離など）を使用することで、無駄な探索を劇的に減らし、最短経路問題を高速に解くことが可能になります。特に、ヒューリスティック関数が実際のコストを過大評価しない（許容的である）場合、必ず最短経路を発見できるという保証（許容性）があります。
具体例・使われ方
A*探索の代表的な利用例としては、カーナビゲーションシステムでのルート検索や、ゲームにおけるキャラクターの自動移動（障害物を避けて目的地へ向かう経路計算）が挙げられます。また、ロボット掃除機が部屋の中を効率よく巡回・移動するための経路計画や、自然言語処理における構文解析の探索プロセスなど、多岐にわたる分野で応用されています。
似た用語との違い
混同されやすい概念として、ダイクストラ法や幅優先探索があります。幅優先探索はすべてのノードを均等に探索し、ダイクストラ法はスタートからの実績コスト g(n) のみを用いて探索を行います。これらに対して、A*探索はゴールまでの予測を立てるヒューリスティック関数 h(n) を組み合わせるため、目的地に向かって「迷わず進む」ような効率的な探索が可能です。つまり、ダイクストラ法は情報がない状態での探索に適しており、A*探索はゴール位置に関する何らかの手がかり（情報）がある場合に最適化された発展形と言えます。
注意点
A*探索の性能は、ヒューリスティック関数の設計に大きく依存します。もし予測コストが実際のコストよりも大きくなってしまう（過大評価する）設計の場合、見つかった経路が必ずしも最短経路にならない可能性があります。また、探索空間が非常に巨大である場合、すべての探索候補をメモリ上に保持（オープンリストとクローズリストの管理）する必要があるため、メモリ消費量が極めて大きくなるという限界があります。