A*アルゴリズム完全ガイド：概要・歴史・原理・実装・応用
エバープレイ編集部A*アルゴリズムとは — 概要と歴史
A*（エースター）アルゴリズムは、最短経路探索（最小コスト経路）を求めるための代表的な探索手法の一つです。1968年に Peter E. Hart、Nils J. Nilsson、Bertram Raphael によって提案され、以降ロボティクス、ゲームプログラミング、地図ルーティング、AIプランニングなど広範な分野で標準的に用いられています。A*は「f(n) = g(n) + h(n)」という評価関数に基づき、現在のノードから始点までの実コスト g(n) と、ノードから目標までの（推定）コスト h(n) を合成して探索の優先度を決定します。
基本原理：f = g + h
A* の中心は評価関数 f(n) = g(n) + h(n) です。ここで
- g(n)：スタートノードからノード n までにかかった既知の最小コスト（これまでの経路コスト）
- h(n)：ノード n からゴールまでの推定残余コスト（ヒューリスティック）
探索はオープンリスト（フロンティア）から f 値が最小のノードを取り出して展開する形で進みます。h が良い推定を与えれば無駄なノード展開を減らせるため、A* は効率的に解を見つけやすくなります。
ヒューリスティック（h）の性質：許容性と一貫性
ヒューリスティックには次の重要な性質があります。
- 許容的（admissible）：どのノードに対しても h(n) が実際の最小残余コストを過大評価しない（≤ 真値）。許容的な h を用いると、A* は木探索（tree search）において最適解を返します。
- 一貫的（consistent / monotone）：任意のエッジ (n → n') に対して h(n) ≤ c(n,n') + h(n') が成り立つ。ここで c(n,n') はエッジコスト。ヒューリスティックが一貫的だと、g 値が増加するにつれて f 値も単調増加し、ノードの再展開（再オープン）が不要になります。グラフ探索（graph search）においては一貫性があると扱いが簡単で効率的です。
注意：許容性は最適性のための十分条件（ツリー探索）ですが、グラフ探索での再開放を避けるためには一貫性が望ましいという点が実務上重要です。
典型的なヒューリスティックの例
- グリッド（上下左右移動のみ）：マンハッタン距離（|dx| + |dy|） — 許容的。
- グリッド（斜め移動あり、斜めコスト = √2）：オクタイル距離やチェビシェフ距離 — 問題設定に応じて許容的に調整。
- 連続空間（ユークリッド距離で移動可能）：ユークリッド距離（直線距離） — 許容的。
- ゼロヒューリスティック：h ≡ 0 の場合、A* はダイクストラ法と同等（最悪のケース）。
擬似コード（基本的な実装イメージ）
open = 優先度付きキュー（f をキー）
closed = 空集合
g[start] = 0
f[start] = h(start)
open.push(start)
while open not empty:
current = open.pop_min_f()
if current is goal:
return reconstruct_path(current)
closed.add(current)
for each neighbor of current:
tentative_g = g[current] + cost(current, neighbor)
if neighbor in closed and tentative_g >= g.get(neighbor, ∞):
continue
if tentative_g < g.get(neighbor, ∞) or neighbor not in open:
cameFrom[neighbor] = current
g[neighbor] = tentative_g
f[neighbor] = tentative_g + h(neighbor)
if neighbor not in open:
open.push(neighbor)
else:
open.decrease_key(neighbor, f[neighbor])
（WordPress に貼る場合は <pre><code> のままでも可。実運用では優先度付きキューの decrease-key 操作に注意。実装言語によっては push duplicates（重複挿入）で代替することも多い。）
計算量・空間量の性質
- 時間計算量：最悪ケースでは指数時間（一般に探索幅 b と最短解の深さ d に対して O(b^d) 的）。ただし h が良ければ大幅に削減される。
- 空間計算量：オープンリストとクローズドリストに多数のノードを保持するためメモリ消費が大きい（多くの実装でボトルネック）。一般にメモリは指数増加する。
- 最適性：ヒューリスティックが許容的であれば A* は（ツリー探索で）最短経路を返す。グラフ探索で一貫性があると再展開なしで最適性を保てる。
派生・改良アルゴリズム
- Weighted A*：f = g + w·h (w > 1)。探索速度を優先して近似解を許容する。許容的な h に対して得られる解のコストは w 倍以内に保証される（サブ最適解の上界）。
- IDA*（Iterative Deepening A*）：メモリ使用量を削減するために f の閾値を反復的に増加させる深さ優先探索ベースの手法。Korf によって提案。メモリ効率は良いがノードの再探索が増える。
- D* / D* Lite / LPA*（増分探索）：動的環境（地図が変化する）や連続的な再計算が必要な場合に既存の探索結果を再利用して効率的に再計算する手法。
- Theta*：可視線（line-of-sight）による斜め経路を許してより自然なパスを生成するグリッド向けの手法。
実装上の注意と最適化テクニック
- 優先度付きキューの選択：binary heap、Fibonnaci heap、あるいは言語標準の priority_queue を用いる。decrease-key をフルサポートしない実装では「重複挿入＋訪問済みチェック」で代替する。
- ハッシュテーブルでの g 値管理：ノードの同定にハッシュ可能なキーを用い、g 値の比較や更新を高速化する。
- タイブレイキング（f が同じときの処理）：f が同値のときは g の大きい方（ = ゴールに近い方）を優先するとノード展開が減ることがある。実装によっては h の小さい方（より目標に近い）を優先する戦略もある。
- ヒューリスティックの改善：ドメイン知識を使ってより強力だが許容的なヒューリスティックを設計できれば探索範囲を大きく削減できる（例：複数ヒューリスティックの最大値を取る複合ヒューリスティックは許容的）。
よくある誤解と落とし穴
- 「許容的＝一貫的」ではない：許容的でも一貫性を満たさないヒューリスティックは存在し、その場合グラフ探索でノードの再オープンが必要になることがある。
- メモリ不足：A* は最短経路を探す一方でメモリを大量に消費するため、特に大域探索や高次元空間では使用に制約がある。IDA* や外部ストレージを併用する戦略を検討する。
- スケーリング：大規模グラフや高密度グリッドでは単純な A* は非現実的な場合があり、階層化検索や事前処理（ランドマーク法、ALT など）による加速が有効。
具体例（格子地図での簡単な説明）
4方向グリッド上でスタート S、ゴール G があり障害物があるとします。マンハッタン距離をヒューリスティックに用いると各ノードの h は到達に必要な最小移動回数を過小評価または等しく見積もるため許容的です。A* はまず S から近傍ノードを展開し、f が小さい順に進み、障害物を回避しつつ効率良く G に到達します。h を 0 にすると全てのノードが g のみによってソートされ、ダイクストラと同じ挙動になります。逆に h を非常に大きく（または g を無視）すると貪欲法（Greedy Best-First Search）に近づき、最短経路を見逃す可能性があります。
応用分野
- ゲームAI（キャラクターの経路探索）
- ロボット経路計画（モバイルロボットのナビゲーション）
- 地図ルーティング（経路案内、交通ネットワーク）
- 組合せ最適化・AIプランニング（状態空間の探索における最良優先探索）
まとめ
A* はヒューリスティックを用いることで Dijkstra の全探索的な無駄を大幅に減らし、実用的な最短経路探索を可能にする強力な手法です。ヒューリスティックの設計（許容性・一貫性）、メモリ管理、優先度キューの実装が性能に直結します。用途に応じて Weighted A*、IDA*、増分探索アルゴリズムなどの派生手法を採用することで、速度とメモリのトレードオフや動的環境への対応が可能です。実装時はヒューリスティックの特性を理解し、グラフ探索かツリー探索かによって適切な取り扱いを行ってください。
参考文献
- P. E. Hart, N. J. Nilsson, B. Raphael, "A Formal Basis for the Heuristic Determination of Minimum Cost Paths" (1968)
- Wikipedia: A* search algorithm
- R.E. Korf, "Depth-first iterative-deepening: An optimal admissible tree search"（IDA* に関する文献）
- A. Stentz, "The focussed D* algorithm for real-time replanning"（D*）
- Stuart Russell & Peter Norvig, "Artificial Intelligence: A Modern Approach"（教科書、A* の章）
投稿者プロフィール
