A*探索（A*アルゴリズム）とは？仕組み・コード・計算量をわかりやすく解説

A*が解く問題

ダイクストラ法は、ゴールから遠ざかる方向も含め、あらゆる方向に距離の輪を広げるようにノードを展開します。ゴールの場所がわかっているなら、これは無駄な作業です。A*はヒューリスティック（残りの距離の推定値）を加えることで、探索をゴールの方向へ引き寄せます。ゲーム、ロボット工学、地図での経路探索の標準的なアルゴリズムです。

A*は、1968年にピーター・ハート（Peter Hart）、ニルス・ニルソン（Nils Nilsson）、バートラム・ラファエル（Bertram Raphael）が "A Formal Basis for the Heuristic Determination of Minimum Cost Paths" で発表しました。

考え方を言葉で説明すると

1. 開始ノードを優先度付きキュー（オープン集合）に、g = 0、f = h(start) で入れます。
2. f が最小のノードを取り出します。それがゴールなら、経路を復元して終了します。
3. 各隣接ノードについて、暫定の g = g(current) + 辺のコスト を計算します。隣接ノードで現在わかっている g より良ければ、それを記録して親を設定し、f = g + h で隣接ノードをプッシュします。
4. オープン集合が空になったら、経路は存在しません。

すべてのノードで h(n) = 0 なら、A*はダイクストラ法とまったく同じになります。完全なヒューリスティックなら、最適な経路をまっすぐにたどります。

ヒューリスティックの選び方

ヒューリスティックが許容的（admissible）であるとは、真の残りコストを過大評価しないことです。すべての辺 n → m について h(n) <= cost(n, m) + h(m) が成り立つとき、無矛盾（consistent、または単調）といいます。無矛盾なヒューリスティックは許容的でもあり、その場合は各ノードの展開が1回で済みます。

グリッド上でのPython実装

下のグリッドは5行7列で、# は列5にある壁を表します。マスは (row, column) で表します。移動は上下左右でコスト1なので、マンハッタン距離は許容的かつ無矛盾です。

import heapq
def a_star(grid, start, goal):
    rows, cols = len(grid), len(grid[0])
    h = lambda p: abs(p[0] - goal[0]) + abs(p[1] - goal[1])
    g = {start: 0}
    parent = {start: None}
    open_heap = [(h(start), start)]
    while open_heap:
        f, cur = heapq.heappop(open_heap)
        if cur == goal:
            path = []
            while cur is not None:
                path.append(cur)
                cur = parent[cur]
            return path[::-1]
        if f > g[cur] + h(cur):
            continue                      # outdated entry
        r, c = cur
        for nb in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nb[0] < rows and 0 <= nb[1] < cols and grid[nb[0]][nb[1]] != "#":
                ng = g[cur] + 1
                if ng < g.get(nb, float("inf")):
                    g[nb] = ng
                    parent[nb] = cur
                    heapq.heappush(open_heap, (ng + h(nb), nb))
    return None
grid = [".......",
        ".....#.",
        ".....#.",
        ".....#.",
        "......."]
path = a_star(grid, (2, 3), (2, 6))
print(len(path) - 1, path)
# 7 [(2, 3), (2, 4), (1, 4), (0, 4), (0, 5), (0, 6), (1, 6), (2, 6)]

具体例で一歩ずつ確認

上のグリッドでは、開始位置 (2, 3) からゴール (2, 6) までは直線で3ステップなので、最初の f は 0 + 3 = 3 です。壁がその直線をふさいでおり、実際の最短経路は7ステップです。A*はこれを段階的に見つけます。f が最小のマスをすべて展開し、それがなくなったら次に小さい f のマスを展開します。

A*は、空いている32マスのうち15マスを展開しました。ダイクストラ法（h = 0 のA*）では、空いているマスがどれも開始位置から高々7ステップ以内にあるため、32マスすべてを展開します。大きく開けた地図では、削減効果ははるかに大きくなります。

時間計算量と空間計算量

メモリを節約する変種にIDA*（反復深化A*）があります。現在の経路だけを保持するかわりに、ノードを再訪問します。

A*を使う場面と実世界での用途

• ゴールが1つで、残りコストの安価で許容的な推定値（地図上の幾何学的な距離など）がある場合にA*を使います。
• 多数または全ノードへの距離が必要な場合や、有用なヒューリスティックがない場合は、ダイクストラ法を使います。重みのないグラフでヒューリスティックの効果が小さい場合は、BFSを使います。
• ビデオゲーム：タイルマップやナビゲーションメッシュ上でのユニットの移動。
• ロボット工学と経路計画：事前計算したランドマークや階層構造と組み合わされることが多くあります。
• パズル解き：ヒューリスティックにタイルのマンハッタン距離を使う8パズルや15パズル。