A* アルゴリズム

A*（エースター）探索アルゴリズムは、グラフ探索アルゴリズムの一つであり、与えられた始点から終点までの最短経路を発見するために用いられる。最良優先探索を拡張し、各ノードnにおける評価関数f(n)として、始点からの実際のコスト(g)と、終点までの推定コスト(h, ヒューリスティック)の和を用いるのが特徴である。

1968年にピーター・ハート(Peter Hart)、ニルス・ニルソン(Nils Nilsson)、バートラム・ラファエル(Bertram Raphael)によって初めて発表された。適切なヒューリスティック関数を用いることで、最適解を保証しつつ、ダイクストラ法よりも高速に動作する。主にビデオゲームにおけるキャラクターの経路探索や、ナビゲーションシステムなどで広く活用されている。

概要

A*アルゴリズムは、各ノードnについて以下の評価関数f(n)を算出し、探索の優先度を決定する。

$f (n) = g (n) + h (n)$

g(n): 始点から現在のノードnに到達するまでにかかった実際のコスト。
h(n): 現在のノードnから終点までの推定コスト。この値を算出する関数を「ヒューリスティック関数」と呼ぶ。
f(n): 始点からノードnを経由して終点に至るまでの総推定コスト。

アルゴリズムは「オープンリスト」と「クローズドリスト」という2つのリストを管理する。オープンリストにはこれから探索する可能性のあるノードを、クローズドリストには探索済みのノードを格納する。アルゴリズムはオープンリストの中から最もf(n)の値が小さいノードを選択し、探索を進めていく。このプロセスを終点に到達するまで繰り返す。

アルゴリズムの流れ

初期化: オープンリストに始点を追加する。始点のg(n)は0、f(n)はヒューリスティック関数によって計算されたh(n)の値とする。
繰り返し:
1. オープンリストからf(n)が最小のノードを選択し、これを現在ノードとする。このノードをオープンリストから削除し、クローズドリストに追加する。
2. 現在ノードが終点であれば、親ノードを逆順にたどって最終的な経路を構築し、探索を終了する。
3. 現在ノードに隣接する各ノードに対して、以下を実行する。
  1. 隣接ノードがクローズドリストに含まれているか、通行不可能な領域であれば無視する。
  2. 隣接ノードがオープンリストにない場合、そのノードをオープンリストに追加する。その際、現在ノードを親ノードとして設定し、g(n)とf(n)を計算する。
  3. 隣接ノードがすでにオープンリストにある場合、現在ノードを経由する方が既存の経路より効率的か（g(n)の値がより小さいか）評価する。より効率的であれば、親ノードとg(n)、f(n)の値を更新する。
オープンリストが空になった場合、それは終点までの経路が存在しないことを意味する。

最適化

実際のソースコードの実装では、明示的なクローズドリスト（Closed List）を別途管理せず、各ノードまでの最小コストを保存する `cost_so_far`（または `g_score`）データ構造を活用して効率を高める手法が頻繁に使用される。

明示的なクローズドリストを除外する手法

この手法は、特定のノードに到達した際のコストをハッシュマップや辞書に保存し、新しい経路を通じて到達したコストが既存の記録より小さい場合のみ、そのノードを更新してオープンリスト（優先度付きキュー）に再挿入する。

メリット
- エッジコストへの対応: 辺（Edge）のコストが一定ではないグラフにおいて、すでに訪問したノードであっても、より短い経路が発見されれば柔軟に経路を更新できるため、最適性を保証しやすい。
- 実装の簡潔さ: 訪問の有無の確認とコスト管理を一つのデータ構造で統合できるため、コードが単純になる。
デメリット
- 優先度付きキューの重複: 同一のノードが異なるコストで優先度付きキューに複数回入る可能性があり、キューのサイズが大きくなり処理オーバーヘッドが発生する場合がある。
- メモリ使用量: すべての訪問候補ノードのコスト情報を保持する必要があるため、単純なセット（Set）ベースのクローズドリストよりもメモリ占有率が高くなる可能性がある。

疑似コード

frontier = PriorityQueue()
frontier.put(start, 0)
came_from = dict()
cost_so_far = dict()
came_from[start] = None
cost_so_far[start] = 0

while not frontier.empty():
    current = frontier.get()

    if current == goal:
        break
    
    for next in graph.neighbors(current):
        new_cost = cost_so_far[current] + graph.cost(current, next)
        if next not in cost_so_far or new_cost < cost_so_far[next]:
            cost_so_far[next] = new_cost
            priority = new_cost + heuristic(goal, next)
            frontier.put(next, priority)
            came_from[next] = current

ヒューリスティック関数 (Heuristic Function)

ヒューリスティック関数の品質は、A*アルゴリズム全体の効率に直接影響する。良いヒューリスティック関数は、終点までの実際のコストを決して上回らない値を返す必要がある。これを「許容的（admissible）ヒューリスティック」と呼び、この条件が満たされるとき、A*は最短経路を保証する。

マンハッタン距離 (Manhattan Distance): グリッド状のマップで、上下左右の4方向にのみ移動可能な場合に主に使用される。
ユークリッド距離 (Euclidean Distance): 2点間の直線距離であり、あらゆる方向への移動が可能な場合に有用である。
対角線距離 (Diagonal Distance): グリッドマップで斜め方向への移動が許される場合に使用される。

特徴

完全性 (Completeness): 解が存在する限り、必ず解を発見する。
最適性 (Optimality): 許容的なヒューリスティック関数を使用すれば、常に最短経路を発見する。
効率性 (Efficiency): 同じヒューリスティックを用いる他の最適なアルゴリズムと比較して、探索するノード数が最小であることが保証される。

応用分野

ゲーム開発: NPCやキャラクターの経路探索（Pathfinding）AIの核心技術として使用される。
ロボティクスとナビゲーション: ロボットの自律走行や最適経路計画に活用される。
ネットワークルーティング: データパケットの最適な転送経路を決定するために応用されうる。
人工知能の問題解決: 8パズルのような多様な探索問題の解を求めるために適用される。

参考文献

概要