A*（えーすたー）

A*アルゴリズムとは

A*（エー・スター）は、グラフ上のノード間における最短経路を見つけるための探索アルゴリズムです。1968年にアルト・アーサーとピーター・ハートレイによって開発されました。ダイクストラ法と同様に、始点から各ノードへのコストを評価しますが、A*はそれに加えて「ヒューリスティック関数」を使用することで、探索の効率を大幅に向上させています。

ヒューリスティック関数

ヒューリスティック関数とは、あるノードから目標ノードまでの「推定コスト」を計算する関数です。この推定コストは、実際のコストよりも小さくなるように設計されており、Aアルゴリズムは、この推定コストと始点から現在のノードまでの実際のコストを組み合わせて、次に探索するノードを決定します。適切なヒューリスティック関数を選択することで、Aはダイクストラ法よりも高速に最短経路を見つけることができます。

アルゴリズムの概要

A*アルゴリズムは、以下の手順で動作します。

1. 始点をオープンリストに追加します。
2. オープンリストから、f(n) = g(n) + h(n) が最小のノードnを選択します（f(n): 評価関数、g(n): 始点からnまでのコスト、h(n): nから目標までの推定コスト）。
3. nが目標ノードであれば、経路を復元して終了します。
4. nをクローズドリストに追加します。
5. nの隣接ノードを調べます。
6. 隣接ノードがオープンリストまたはクローズドリストに存在しない場合、g(n) + cost(n, neighbor) を計算し、h(neighbor) を計算して f(neighbor) を求め、neighbor をオープンリストに追加します。
7. 隣接ノードがオープンリストまたはクローズドリストに存在する場合、新しい経路の方がコストが低いかどうかを調べ、コストが低い場合は経路を更新します。
8. オープンリストが空になるまで、手順2〜7を繰り返します。

A*アルゴリズムの応用例

A*アルゴリズムは、様々な分野で応用されています。

• ゲームAI: キャラクターの経路探索
• ロボット工学: ロボットの経路計画
• 地図ナビゲーション: 最短経路の計算
• ネットワークルーティング: データパケットの最適な経路選択

注意点

ヒューリスティック関数の選択は、A*アルゴリズムの性能に大きく影響します。不適切なヒューリスティック関数を使用すると、最短経路を見つけられない場合があります。