> [!abstract] Introduction > A\* 알고리즘은 시작 노드에서 목표 노드까지의 최단 경로를 찾는 알고리즘입니다. 이미 지나온 실제 비용 $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이 로봇 Shakey[^shakey-project]의 자율 경로 계획을 위해 개발했으며, 이후 게임 AI, 자율 주행, 물류 최적화 등 경로 탐색이 필요한 거의 모든 분야에서 표준처럼 쓰이고 있다. ## 평가 함수 $f(n) = g(n) + h(n)$ A\*의 핵심은 평가 함수 $f(n)$이다. 각 노드 $n$에 대해 다음 세 값을 관리한다. ![[astarEvalFunction.svg]] $f(n) = g(n) + h(n)$ $g(n)$은 시작 노드에서 $n$까지 실제로 거쳐온 경로의 누적 비용이다. 탐색이 진행되면서 더 짧은 경로가 발견되면 갱신된다. $h(n)$은 $n$에서 목표까지 남은 비용의 **추정치**로, 이를 휴리스틱 함수(*heuristic function*)라 부른다. $f(n)$은 $g(n)$과 $h(n)$의 합으로, "이 노드를 거치는 전체 경로의 추정 총비용"을 의미한다. A\*는 [[Priority Queue|우선순위 큐]]에서 $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'$으로의 이동 비용이다. 일관성은 삼각 부등식[^triangle-inequality]의 한 형태로, "한 걸음 이동할 때 $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이다. 휴리스틱으로는 맨해튼 거리를 사용한다. ![[astarGridSetup.svg]] ### Step 1 — 시작 노드 확장 ![[astarStep1.svg]] 시작 노드 `S`(0,0)의 $g = 0$, $h = |0-4| + |0-4| = 8$이므로 $f = 8$이다. Open 리스트에서 $f$가 가장 작은 이 노드를 꺼내 확장한다. 인접한 (0,1)이 Open 리스트에 추가된다. 아래쪽 (1,0)은 벽이라 건너뛴다. ### Step 4 — 벽을 따라 우회 ![[astarStep2.svg]] (0,3)까지 확장하면서 $f = 8$이 유지된다. $g$가 1씩 증가하는 만큼 $h$가 정확히 1씩 감소하기 때문이다. 직선 구간에서는 맨해튼 휴리스틱이 실제 잔여 비용과 정확히 일치하므로 $f$가 변하지 않는다. 이 구간의 모든 노드가 최적 경로 위에 있다는 뜻이다. ### Step 9 — 우회 구간에서 $f$ 값 상승 ![[astarStep3.svg]] (2,2)에 도달하면 $g = 8$, $h = 4$로 $f = 12$가 된다. 벽 때문에 되돌아가야 하는 구간에서는 $g$가 빠르게 증가하는 반면 $h$는 느리게 감소하므로 $f$가 상승한다. 이 $f$ 값의 변화가 핵심이다 — 만약 다른 경로가 있었다면 A\*는 $f$가 더 낮은 그 경로를 먼저 탐색했을 것이다. ### Step 16 — 목표 직전 ![[astarStep4.svg]] (4,3)에서 $g = 15$, $h = 1$, $f = 16$이다. 마지막 한 칸만 남았다. 최종 경로의 총 비용이 16이 될 것임을 이미 알 수 있다. ### 최종 결과 ![[astarFinalPath.svg]] A\*가 찾은 최단 경로는 비용 16이며, 전체 17개 노드만 방문했다[^serpentine-note]. 벽이 없는 노드는 총 21개인데, 그 중 4개는 방문하지 않았다. 이 격자에서는 모든 경로가 같은 비용을 가지므로 A\*의 가지치기 효과가 두드러지지 않지만, 여러 갈래가 있는 복잡한 그래프에서는 $f$ 값이 높은 가지를 일찍 포기하여 탐색 공간을 크게 줄인다. ## 의사코드 아래는 AIMA (Russell & Norvig, 2021)의 BEST-FIRST-SEARCH를 $f(n) = g(n) + h(n)$으로 특수화한 A\*의 의사코드다[^aima-pseudocode]. ``` 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`([[Priority Queue|우선순위 큐]])에 넣는다. 2. `frontier`에서 $f$가 가장 작은 노드를 꺼낸다. 3. 꺼낸 노드가 목표이면 경로를 반환한다. 4. 그렇지 않으면 인접 노드를 확장하고, 더 짧은 경로가 발견된 경우에만 `reached` 테이블을 갱신하여 `frontier`에 추가한다. 5. `frontier`가 빌 때까지 반복한다. 빈 채로 종료되면 경로가 존재하지 않는 것이다. `reached` 테이블은 이미 발견한 노드의 최소 $g$ 값을 기록하여, 같은 노드를 더 비싼 경로로 중복 탐색하는 것을 방지한다. ## Python 구현 위 의사코드를 Python으로 구현하면 아래와 같다. [[Heap|힙]] 기반의 `heapq` 모듈로 [[Priority Queue|우선순위 큐]]를 구현한다. ```python 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. [^shakey-project]: Shakey the Robot — 스탠포드 연구소(SRI International)에서 1966~1972년에 개발한 세계 최초의 범용 이동 로봇. A\*, STRIPS 등 AI 역사에서 중요한 알고리즘들이 이 프로젝트에서 탄생했다. [^triangle-inequality]: 삼각 부등식(*triangle inequality*) — 삼각형의 한 변의 길이는 나머지 두 변의 길이의 합보다 작거나 같다는 기하학적 성질. 일관성 조건에서는 "직접 가는 추정치가 한 걸음 돌아가서 추정하는 것보다 항상 작거나 같다"는 의미로 쓰인다. [^serpentine-note]: 이 구불구불한(*serpentine*) 격자에서는 벽 배치 때문에 모든 경로의 비용이 동일하여, A\*가 가지치기 없이 거의 모든 노드를 방문한다. 실제 응용에서는 여러 갈래가 존재하므로 A\*의 가지치기 효과가 훨씬 크게 나타난다. [^aima-pseudocode]: Russell and Norvig (2021), Figure 3.7 BEST-FIRST-SEARCH를 $f = g + h$로 특수화한 형태. 원서에서는 A\*를 별도 함수로 분리하지 않고 best-first search의 인스턴스로 기술한다.