Introduction

A* 알고리즘은 시작 노드에서 목표 노드까지의 최단 경로를 찾는 알고리즘입니다. 이미 지나온 실제 비용 g(n)g(n)과 앞으로 남은 추정 비용 h(n)h(n)을 더한 평가 함수 f(n)=g(n)+h(n)f(n) = g(n) + h(n)을 사용하여, 가장 유망한 노드부터 탐색합니다. 허용 가능한 휴리스틱을 사용하면 최적 해를 보장한다는 점에서, 무정보 탐색(BFS, Dijkstra)과 탐욕적 탐색(Greedy Best-First)의 장점을 결합한 알고리즘이라 할 수 있습니다. 이 글에서는 A*가 필요한 이유, 평가 함수와 허용 가능한 휴리스틱의 조건, 알고리즘의 동작 과정, 그리고 시간·공간 복잡도를 살펴봅니다.

왜 A*인가?

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

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

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

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

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

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

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

허용 가능한 휴리스틱

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

허용 가능성 (Admissibility)

∀n:h(n)≤h∗(n)\forall n : h(n) \leq h^*(n)

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

일관성 (Consistency)

∀n,n′:h(n)≤c(n,n′)+h(n′)\forall n, n' : h(n) \leq c(n, n') + h(n')

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

대표적인 휴리스틱 함수

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

맨해튼 거리

h(n)=∣xn−xg∣+∣yn−yg∣h(n) = |x_n - x_g| + |y_n - y_g|

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

유클리드 거리

h(n)=(xn−xg)2+(yn−yg)2h(n) = \sqrt{(x_n - x_g)^2 + (y_n - y_g)^2}

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

체비셰프 거리

h(n)=max⁡(∣xn−xg∣,∣yn−yg∣)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=0g = 0, h=∣0−4∣+∣0−4∣=8h = |0-4| + |0-4| = 8이므로 f=8f = 8이다. Open 리스트에서 ff가 가장 작은 이 노드를 꺼내 확장한다. 인접한 (0,1)이 Open 리스트에 추가된다. 아래쪽 (1,0)은 벽이라 건너뛴다.

Step 4 — 벽을 따라 우회

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

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

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

Step 16 — 목표 직전

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

최종 결과

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

의사코드

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

\begin{algorithm}
\caption{A* 탐색}
\begin{algorithmic}
\Require 문제 $problem$, 휴리스틱 $h$
\Ensure 해 또는 실패
\Function{A*-Search}{$problem, h$}
    \State $node \gets \text{Node}(\text{state}{=}problem.\text{initial},\ \text{path-cost}{=}0)$
    \State $frontier \gets$ $f = g + h$ 순서의 우선순위 큐, 원소는 $node$ 하나
    \State $reached \gets$ 항목이 하나인 조회 표 $\{problem.\text{initial}: node\}$
    \While{$frontier \neq \emptyset$}
        \State $node \gets \text{Pop}(frontier)$ \Comment{$f$가 가장 작은 노드}
        \If{$problem.\text{Is-Goal}(node.\text{state})$}
            \Return $\text{Solution}(node)$
        \EndIf
        \ForAll{$child \in \text{Expand}(problem, node)$}
            \State $s \gets child.\text{state}$
            \If{$s \notin reached$ \OR $child.\text{path-cost} < reached[s].\text{path-cost}$}
                \State $reached[s] \gets child$
                \State $child$를 $frontier$에 추가
            \EndIf
        \EndFor
    \EndWhile
    \Return $failure$
\EndFunction
\end{algorithmic}
\end{algorithm}

핵심 흐름은 다음과 같다.

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

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

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

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

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

시간 복잡도와 공간 복잡도

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

시간 복잡도

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

공간 복잡도

공간 복잡도 역시 최악의 경우 O(bd)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+hf = g + h로 특수화한 형태. 원서에서는 A*를 별도 함수로 분리하지 않고 best-first search의 인스턴스로 기술한다. ↩