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, 또는 단조적)이라고 합니다. 일관적인 휴리스틱은 허용 가능하기도 하며, 이 경우 각 노드를 한 번만 확장하면 됩니다.

격자에서의 파이썬 구현

아래 격자는 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*를 쓰는 경우와 실제 활용

• 목표가 하나이고, 지도의 기하학적 거리처럼 저렴하고 허용 가능한 남은 비용 추정값이 있을 때 A*를 사용합니다.
• 많은 노드 또는 모든 노드까지의 거리가 필요하거나 쓸 만한 휴리스틱이 없다면 다익스트라를 사용하세요. 휴리스틱의 이점이 적은 가중치 없는 그래프에는 BFS를 사용합니다.
• 비디오 게임: 타일 맵과 내비게이션 메시에서의 유닛 이동.
• 로보틱스와 경로 계획: 미리 계산한 랜드마크나 계층 구조와 함께 쓰는 경우가 많습니다.
• 퍼즐 풀이: 타일의 맨해튼 거리를 휴리스틱으로 쓰는 8퍼즐과 15퍼즐.