A*

왜 A*인가?

내비게이션 앱으로 목적지까지의 경로를 검색한다고 하자. 단순히 "지금까지 얼마나 왔는지"만 보면 이미 먼 길을 돌아온 경로도 계속 탐색하게 된다. 반대로 "목적지까지 얼마나 남았는지"만 보면 눈앞에 산이 있어도 직선으로 돌진하려 한다. A*는 이 두 가지 정보를 합쳐서 "전체 비용이 가장 적을 것 같은 길"부터 탐색하는 알고리즘이다.

1968년 스탠포드 연구소의 Peter Hart, Nils Nilsson, Bertram Raphael이 로봇 Shakey¹의 자율 경로 계획을 위해 개발했으며, 이후 게임 AI, 자율 주행, 물류 최적화 등 경로 탐색이 필요한 거의 모든 분야에서 표준처럼 쓰이고 있다.

평가 함수 $f(n) = g(n) + h(n)$

A*의 핵심은 평가 함수 $f(n)$이다. 각 노드 $n$에 대해 다음 세 값을 관리한다.

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

$g(n)$은 시작 노드에서 $n$까지 실제로 거쳐온 경로의 누적 비용이다. 탐색이 진행되면서 더 짧은 경로가 발견되면 갱신된다. $h(n)$은 $n$에서 목표까지 남은 비용의 추정치로, 이를 휴리스틱 함수(heuristic function)라 부른다. $f(n)$은 $g(n)$과 $h(n)$의 합으로, "이 노드를 거치는 전체 경로의 추정 총비용"을 의미한다.

A*는 우선순위 큐에서 $f(n)$이 가장 작은 노드를 꺼내어 확장한다. 이것이 A*가 Best-First Search의 한 형태인 이유다. $h(n) = 0$으로 설정하면 Uniform-Cost Search(Dijkstra 알고리즘의 그래프 탐색 버전)와 동일하게 동작하고, $g(n) = 0$으로 설정하면 Greedy Best-First Search가 된다. 즉 A*는 이 두 알고리즘을 일반화한 것이다.

허용 가능한 휴리스틱

A*가 최적 해를 보장하려면 휴리스틱 $h(n)$이 두 가지 조건을 만족해야 한다.

허용 가능성 (Admissibility)

$\forall n : h(n) \leq h^*(n)$

$h^*(n)$은 $n$에서 목표까지의 실제 최소 비용이다. 허용 가능한 휴리스틱은 실제 비용을 절대 과대평가하지 않는다. 쉽게 말해, "낙관적인 추정"만 허용된다. 과대평가하면 진짜 최단 경로를 건너뛰고 더 긴 경로를 선택할 위험이 생긴다.

일관성 (Consistency)

$\forall n, n' : h(n) \leq c(n, n') + h(n')$

$c(n, n')$은 $n$에서 이웃 $n'$으로의 이동 비용이다. 일관성은 삼각 부등식²의 한 형태로, "한 걸음 이동할 때 $h$가 이동 비용 이상으로 감소하지 않는다"는 뜻이다. 일관성을 만족하면 허용 가능성도 자동으로 만족하며, 한번 closed에 들어간 노드를 다시 열 필요가 없어 구현이 단순해진다.

대표적인 휴리스틱 함수

격자(grid) 환경에서 자주 쓰이는 휴리스틱은 다음과 같다. 세 함수 모두 실제 최단 거리를 과대평가하지 않으므로 허용 가능하며, 동시에 일관적이다.

맨해튼 거리

$h(n) = |x_n - x_g| + |y_n - y_g|$

상하좌우 4방향 이동만 가능할 때 사용한다.

유클리드 거리

$h(n) = \sqrt{(x_n - x_g)^2 + (y_n - y_g)^2}$

임의의 방향으로 이동할 수 있을 때 사용한다.

체비셰프 거리

$h(n) = \max(|x_n - x_g|, |y_n - y_g|)$

8방향(대각선 포함) 이동이 가능하고 대각선 비용이 직선 비용과 동일할 때 사용한다.

알고리즘 동작 과정

아래 5×5 격자에서 A*가 시작 노드 S(0,0)에서 목표 노드 G(4,4)까지의 최단 경로를 찾는 과정을 단계별로 살펴보자. 벽(✕)은 통과할 수 없고, 상하좌우로만 이동할 수 있으며, 이동 비용은 모두 1이다. 휴리스틱으로는 맨해튼 거리를 사용한다.

Step 1 — 시작 노드 확장

시작 노드 S(0,0)의 $g = 0$, $h = |0-4| + |0-4| = 8$이므로 $f = 8$이다. Open 리스트에서 $f$가 가장 작은 이 노드를 꺼내 확장한다. 인접한 (0,1)이 Open 리스트에 추가된다. 아래쪽 (1,0)은 벽이라 건너뛴다.

Step 4 — 벽을 따라 우회

(0,3)까지 확장하면서 $f = 8$이 유지된다. $g$가 1씩 증가하는 만큼 $h$가 정확히 1씩 감소하기 때문이다. 직선 구간에서는 맨해튼 휴리스틱이 실제 잔여 비용과 정확히 일치하므로 $f$가 변하지 않는다. 이 구간의 모든 노드가 최적 경로 위에 있다는 뜻이다.

Step 9 — 우회 구간에서 $f$ 값 상승

(2,2)에 도달하면 $g = 8$, $h = 4$로 $f = 12$가 된다. 벽 때문에 되돌아가야 하는 구간에서는 $g$가 빠르게 증가하는 반면 $h$는 느리게 감소하므로 $f$가 상승한다. 이 $f$ 값의 변화가 핵심이다 — 만약 다른 경로가 있었다면 A*는 $f$가 더 낮은 그 경로를 먼저 탐색했을 것이다.

Step 16 — 목표 직전

(4,3)에서 $g = 15$, $h = 1$, $f = 16$이다. 마지막 한 칸만 남았다. 최종 경로의 총 비용이 16이 될 것임을 이미 알 수 있다.

최종 결과

A*가 찾은 최단 경로는 비용 16이며, 전체 17개 노드만 방문했다³. 벽이 없는 노드는 총 21개인데, 그 중 4개는 방문하지 않았다. 이 격자에서는 모든 경로가 같은 비용을 가지므로 A*의 가지치기 효과가 두드러지지 않지만, 여러 갈래가 있는 복잡한 그래프에서는 $f$ 값이 높은 가지를 일찍 포기하여 탐색 공간을 크게 줄인다.

의사코드

아래는 AIMA (Russell & Norvig, 2021)의 BEST-FIRST-SEARCH를 $f(n) = g(n) + h(n)$으로 특수화한 A*의 의사코드다⁴.

function A*-SEARCH(problem, h) returns solution or failure
    node ← NODE(STATE=problem.INITIAL, PATH-COST=0)
    frontier ← priority queue ordered by f = g + h, with node as the only element
    reached ← a lookup table, with one entry: {problem.INITIAL: node}

    while frontier is not empty do
        node ← POP(frontier)            ▷ f가 가장 작은 노드
        if problem.IS-GOAL(node.STATE) then
            return SOLUTION(node)

        for each child in EXPAND(problem, node) do
            s ← child.STATE
            if s is not in reached  or  child.PATH-COST < reached[s].PATH-COST then
                reached[s] ← child
                add child to frontier

    return failure

핵심 흐름은 다음과 같다.

1. 시작 노드를 frontier(우선순위 큐)에 넣는다.
2. frontier에서 $f$가 가장 작은 노드를 꺼낸다.
3. 꺼낸 노드가 목표이면 경로를 반환한다.
4. 그렇지 않으면 인접 노드를 확장하고, 더 짧은 경로가 발견된 경우에만 reached 테이블을 갱신하여 frontier에 추가한다.
5. frontier가 빌 때까지 반복한다. 빈 채로 종료되면 경로가 존재하지 않는 것이다.

reached 테이블은 이미 발견한 노드의 최소 $g$ 값을 기록하여, 같은 노드를 더 비싼 경로로 중복 탐색하는 것을 방지한다.

Python 구현

위 의사코드를 Python으로 구현하면 아래와 같다. 힙 기반의 heapq 모듈로 우선순위 큐를 구현한다.

import heapq
from typing import Optional


def astar(
    grid: list[list[int]],
    start: tuple[int, int],
    goal: tuple[int, int],
) -> Optional[list[tuple[int, int]]]:
    """A* 최단 경로 탐색.

    Args:
        grid:  2차원 리스트. 0이면 이동 가능, 1이면 벽.
        start: 시작 좌표 (행, 열).
        goal:  목표 좌표 (행, 열).

    Returns:
        시작→목표 최단 경로(좌표 리스트). 경로가 없으면 None.
    """
    rows, cols = len(grid), len(grid[0])

    def heuristic(a: tuple[int, int], b: tuple[int, int]) -> int:
        """맨해튼 거리 — 허용 가능하고 일관적인 휴리스틱."""
        return abs(a[0] - b[0]) + abs(a[1] - b[1])

    # (f, 삽입순서, 좌표)  — 삽입순서는 f가 같을 때 FIFO를 보장
    counter = 0
    open_list = [(heuristic(start, goal), counter, start)]
    came_from: dict[tuple[int, int], tuple[int, int]] = {}
    g_score: dict[tuple[int, int], int] = {start: 0}
    closed: set[tuple[int, int]] = set()

    while open_list:
        f, _, current = heapq.heappop(open_list)

        if current in closed:          # 이미 최적으로 확장된 노드
            continue
        if current == goal:            # 목표 도달 → 경로 역추적
            path = []
            node = goal
            while node in came_from:
                path.append(node)
                node = came_from[node]
            path.append(start)
            return path[::-1]

        closed.add(current)
        r, c = current

        for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nr, nc = r + dr, c + dc
            neighbor = (nr, nc)

            if not (0 <= nr < rows and 0 <= nc < cols):
                continue                # 격자 범위 초과
            if grid[nr][nc] == 1 or neighbor in closed:
                continue                # 벽이거나 이미 확장 완료

            tentative_g = g_score[current] + 1

            if tentative_g < g_score.get(neighbor, float("inf")):
                came_from[neighbor] = current
                g_score[neighbor] = tentative_g
                f_new = tentative_g + heuristic(neighbor, goal)
                counter += 1
                heapq.heappush(open_list, (f_new, counter, neighbor))

    return None  # 경로 없음

몇 가지 구현 포인트를 짚어보자.

heapq는 최소 힙min-heap이므로, 튜플의 첫 번째 원소인 $f$ 값이 작은 것부터 꺼내진다. 두 번째 원소 counter는 $f$가 동일할 때 삽입 순서대로 꺼내기 위한 타이브레이커(tiebreaker)다. 이 장치가 없으면 좌표 튜플끼리 비교를 시도하다가 예기치 않은 결과를 낳을 수 있다.

closed 집합은 이미 최적 비용으로 확장이 완료된 노드를 추적한다. 일관적인 휴리스틱을 사용하면 한번 closed에 들어간 노드의 $g$ 값은 더 이상 갱신되지 않으므로, closed 검사만으로 중복 확장을 방지할 수 있다.

경로 역추적path reconstruction은 came_from 딕셔너리를 통해 목표에서 시작까지 부모를 따라가며 구성한다. 마지막에 [::-1]로 뒤집어 시작 → 목표 순서로 반환한다.

시간 복잡도와 공간 복잡도

A*의 복잡도는 휴리스틱의 품질에 크게 좌우된다.

시간 복잡도

시간 복잡도는 최악의 경우 $O(b^d)$이다. 여기서 $b$는 분기 계수(branching factor), $d$는 최적 해의 깊이다. 하지만 휴리스틱이 정확할수록 실제 탐색 노드 수는 크게 줄어든다. 만약 $h(n) = h^*(n)$(완벽한 휴리스틱)이라면 A*는 최적 경로 위의 노드만 확장하므로 $O(d)$에 수렴한다. 반대로 $h(n) = 0$이면 Dijkstra와 동일해진다.

공간 복잡도

공간 복잡도 역시 최악의 경우 $O(b^d)$이다. 탐색한 모든 노드를 메모리에 보관해야 하기 때문이다. 이 메모리 문제가 A*의 가장 큰 한계이며, 이를 극복하기 위해 IDA*(Iterative Deepening A*), SMA*(Simplified Memory-Bounded A*) 등의 변형이 등장했다. 이들은 별도의 포스트에서 다룬다.

---

출처

• Hart, P. E., Nilsson, N. J. and Raphael, B. (1968) 'A Formal Basis for the Heuristic Determination of Minimum Cost Paths', IEEE Transactions on Systems Science and Cybernetics, 4(2), pp. 100–107.
• Russell, S. and Norvig, P. (2021) Artificial Intelligence: A Modern Approach. 4th Global edn. Harlow: Pearson. Chapter 3.5.2.
• Amit Patel (2023) Introduction to A*. Red Blob Games. Available at: https://www.redblobgames.com/pathfinding/a-star/introduction.html.

Footnotes

1. Shakey the Robot — 스탠포드 연구소(SRI International)에서 1966~1972년에 개발한 세계 최초의 범용 이동 로봇. A*, STRIPS 등 AI 역사에서 중요한 알고리즘들이 이 프로젝트에서 탄생했다. ↩

2. 삼각 부등식(triangle inequality) — 삼각형의 한 변의 길이는 나머지 두 변의 길이의 합보다 작거나 같다는 기하학적 성질. 일관성 조건에서는 "직접 가는 추정치가 한 걸음 돌아가서 추정하는 것보다 항상 작거나 같다"는 의미로 쓰인다. ↩

3. 이 구불구불한(serpentine) 격자에서는 벽 배치 때문에 모든 경로의 비용이 동일하여, A*가 가지치기 없이 거의 모든 노드를 방문한다. 실제 응용에서는 여러 갈래가 존재하므로 A*의 가지치기 효과가 훨씬 크게 나타난다. ↩

4. Russell and Norvig (2021), Figure 3.7 BEST-FIRST-SEARCH를 $f = g + h$로 특수화한 형태. 원서에서는 A*를 별도 함수로 분리하지 않고 best-first search의 인스턴스로 기술한다. ↩