A* 알고리즘: 휴리스틱으로 경로 탐색 범위를 줄이는 방법
A* 알고리즘의 f(n)=g(n)+h(n) 평가 함수, 허용·일관 휴리스틱 조건, 경로 탐색 운영 방식과 Python 격자 구현을 정리한다.
2026-08-14 · 최초 발행 2024-04-29
경로를 향해 탐색 범위를 좁히는 평가 함수
A*는 시작점에서 목표까지의 최적 또는 준최적 경로를 찾기 위해 휴리스틱을 사용하는 탐색 알고리즘이다. 도로 네비게이션, 로봇 경로 계획, 게임 AI에서 널리 쓰이며, 핵심은 f(n)=g(n)+h(n) 평가 함수와 휴리스틱 품질에 있다.
g(n)은 시작점에서 현재 노드까지 쌓인 비용이고, h(n)은 현재 노드에서 목표까지 필요한 비용의 추정값이다. 두 값을 더한 f(n)이 다음에 확장할 노드의 우선순위를 정한다.
후보 노드는 우선순위 큐인 Open set에서 관리하고, 탐색이 확정된 노드는 Closed set에 둔다. 각 노드의 g, f, 부모 정보를 갱신해 두면 목표에 도달했을 때 부모 포인터를 따라 경로를 복원할 수 있다.
휴리스틱 h(n)이 실제 비용을 넘지 않는 허용성(admissible)과 h(n) ≤ c(n,m)+h(m)을 만족하는 일관성(consistency/monotone)을 지키면 최적 경로를 보장할 수 있다. 이때 엣지 비용은 비음수여야 하며, 일관성은 이미 확정한 노드를 다시 여는 작업을 최소화한다.
h ≡ 0인 경우 A*는 Dijkstra 알고리즘과 같고, g ≡ 0이면 Greedy Best-First Search가 된다. 휴리스틱이 더 많은 정보를 제공할수록 불필요한 탐색 공간은 줄어든다.
휴리스틱과 상태 갱신이 탐색 품질을 좌우한다
격자 이동에는 맨해튼 거리, 유클리드 거리, 8방향 이동에는 옥타일 거리처럼 문제 공간의 이동 모델에 맞는 휴리스틱을 선택해야 한다. 허용성과 일관성이 유지되면 최적성을 보장할 수 있고, Weighted A* 같은 변형은 속도와 최적성 사이의 선택지를 제공한다.
Open set은 보통 최소 힙 기반 우선순위 큐로 운영한다. 더 작은 g를 찾았으면 부모, g, f를 다시 계산하고 해당 노드를 재삽입해야 한다. 일관 휴리스틱을 쓸 때는 노드가 처음 pop되는 시점의 g가 최적값이 되므로 재열기를 줄일 수 있다.
비음수 가중치 조건에서는 완전성을 확보한다. 우선순위 큐를 쓰는 경우 시간 복잡도는 O(E log V) 경향이고, 메모리 복잡도는 O(V) 규모다. 휴리스틱의 정보성이 높으면 확장 노드 수가 크게 줄며, 실측 환경에서는 Dijkstra 대비 3~50배까지 확장 수가 감소한 사례가 빈번하다.
격자 대칭성을 활용하는 Jump Point Search(JPS), 랜드마크와 삼각부등식을 이용하는 ALT 휴리스틱은 탐색 규모를 줄이는 확장 방식이다. Weighted A*는 f=g+w·h, w≥1로 우선순위를 조정하며, 속도를 얻는 대신 가중치에 비례한 최적성을 포기한다.
도로망·게임·로봇에서 달라지는 비용 모델
도로 네비게이션에서는 교차로를 노드, 도로를 엣지로 보고 예상 주행시간을 가중치로 둔다. 이 가중치는 거리, 속도, 교통량을 반영한다. 직선거리와 최고속도를 이용한 추정이나 랜드마크 기반 하한값을 휴리스틱으로 쓸 수 있으며, 실시간 트래픽이 바뀌면 엣지 가중치를 갱신한 뒤 A*를 다시 질의하거나 증분형 계획을 적용한다.
게임 AI의 타일 격자에서는 장애물과 지형 비용이 탐색 비용에 들어간다. 4방향 이동에는 맨해튼 거리, 8방향 이동에는 옥타일 거리가 맞으며, JPS나 네비메시(navmesh)의 포털 그래프와 A*를 결합하는 구성이 가능하다.
로보틱스와 자율주행은 비용맵(costmap)에 충돌 회피와 안전 마진을 반영한다. A*가 전역 경로를 산출하고 로컬 플래너가 동적 장애물에 대응하는 역할 분리가 일반적이다. 일관 휴리스틱 보장, 동적 재계획 주기, 시간 창 제어가 안전성에 영향을 준다.
같은 맵에서 휴리스틱 정보성에 따라 Dijkstra 대비 노드 확장 수를 520배 줄일 수 있고, 평균 응답 시간이 3080% 단축된 사례도 관측된다. w=1에서는 최적성이 보장되며, 운영 정책에 따라 속도 우선과 품질 우선 모드를 전환할 수 있다. 일관 휴리스틱과 비음수 비용 가정 아래에서는 재현성을 확보하고, 대규모 그래프에서는 우선순위 큐와 캐시 전략으로 확장성을 확보한다.
Open set에서 목표까지 이어지는 흐름
입력은 그래프 또는 격자, 시작·목표 노드, 비용 함수, 휴리스틱 h(n)이다. Open set을 초기화한 뒤 가장 작은 f를 가진 노드를 꺼내고, 목표인지 검사한다. 목표가 아니면 이웃의 g, f를 갱신해 다시 넣거나 확정한다. 결과는 노드 열로 된 경로, 총 비용, 확장 수 같은 통계다.
시작점이나 목표점이 차단되어 있는지 먼저 검증해야 하며, 엣지 비용이 비음수인지도 확인해야 한다. 일관 휴리스틱을 만족하지 못하는 환경에서는 노드를 다시 열 수 있는 로직이 필요하다.
격자 맵에서 동작하는 Python 구현
이 구현은 Python 3.10+와 표준 라이브러리 heapq만 사용한다. 0은 이동 가능한 칸, 1은 장애물이며 4/8방향 이동을 지원한다. 휴리스틱으로 manhattan, octile, euclidean을 선택할 수 있다.
from __future__ import annotations
import math
import heapq
from typing import List, Tuple, Optional, Callable, Dict
Grid = List[List[int]]
Pos = Tuple[int, int]
def manhattan(a: Pos, b: Pos) -> float:
return abs(a[0] - b[0]) + abs(a[1] - b[1])
def euclidean(a: Pos, b: Pos) -> float:
dx, dy = a[0] - b[0], a[1] - b[1]
return math.hypot(dx, dy)
def octile(a: Pos, b: Pos) -> float:
# 8방향 이동에서 (1, sqrt(2)) 비용 체계에 대한 허용 휴리스틱
dx, dy = abs(a[0] - b[0]), abs(a[1] - b[1])
F = math.sqrt(2) - 1
return (dx + dy) + (F - 1) * min(dx, dy)
def astar(
grid: Grid,
start: Pos,
goal: Pos,
*,
diag: bool = False,
heuristic: str = "auto",
w: float = 1.0,
allow_reopen: bool = True,
return_stats: bool = True,
) -> Tuple[Optional[List[Pos]], float, Dict[str, int]]:
"""
A* 경로 탐색기.
- grid: 0=통과, 1=장애물
- diag: 8방향 이동 허용 여부
- heuristic: 'auto'|'manhattan'|'euclidean'|'octile'
- w: Weighted A* 가중치 (>=1.0에서 최적성 포기 가능)
- allow_reopen: 일관 휴리스틱이 아닐 때 노드 재열기 허용
"""
rows, cols = len(grid), len(grid[0])
def in_bounds(p: Pos) -> bool:
r, c = p
return 0 <= r < rows and 0 <= c < cols
def passable(p: Pos) -> bool:
r, c = p
return grid[r][c] == 0
if not in_bounds(start) or not in_bounds(goal):
raise ValueError("start/goal 좌표 범위 오류")
if not passable(start) or not passable(goal):
raise ValueError("start/goal 위치가 차단됨")
# 이웃 생성자
if diag:
neighbors_delta = [(-1,0),(1,0),(0,-1),(0,1),(-1,-1),(-1,1),(1,-1),(1,1)]
else:
neighbors_delta = [(-1,0),(1,0),(0,-1),(0,1)]
def neighbors(p: Pos):
pr, pc = p
for dr, dc in neighbors_delta:
q = (pr + dr, pc + dc)
if in_bounds(q) and passable(q):
yield q
# 이동 비용
def step_cost(a: Pos, b: Pos) -> float:
# 대각선 이동 비용 sqrt(2), 직교 이동 비용 1
if a[0] != b[0] and a[1] != b[1]:
return math.sqrt(2)
return 1.0
# 휴리스틱 선택
if heuristic == "auto":
hfun = manhattan if not diag else octile
elif heuristic == "manhattan":
hfun = manhattan
elif heuristic == "euclidean":
hfun = euclidean
elif heuristic == "octile":
hfun = octile
else:
raise ValueError("알 수 없는 heuristic")
# A* 본체
g: Dict[Pos, float] = {start: 0.0}
parent: Dict[Pos, Optional[Pos]] = {start: None}
counter = 0 # tie-breaker
open_heap: List[Tuple[float, float, float, int, Pos]] = []
def f_score(p: Pos) -> float:
return g.get(p, math.inf) + w * hfun(p, goal)
# tie-breaking: (f, h, g, counter, pos)
heapq.heappush(open_heap, (f_score(start), hfun(start, goal), 0.0, counter, start))
open_set = {start}
closed_set = set()
expanded = 0
pushed = 1
while open_heap:
_, _, _, _, n = heapq.heappop(open_heap)
if n not in open_set:
continue
open_set.remove(n)
if n == goal:
# 경로 복원
path = []
cur = n
while cur is not None:
path.append(cur)
cur = parent[cur]
path.reverse()
stats = {"expanded": expanded, "pushed": pushed, "path_len": len(path)}
return path, g[n], stats
closed_set.add(n)
expanded += 1
for m in neighbors(n):
if not allow_reopen and m in closed_set:
continue
tentative_g = g[n] + step_cost(n, m)
if tentative_g < g.get(m, math.inf):
parent[m] = n
g[m] = tentative_g
# 재열기 허용 시 closed라도 갱신
if m in closed_set:
closed_set.remove(m)
counter += 1
heapq.heappush(open_heap, (f_score(m), hfun(m, goal), g[m], counter, m))
open_set.add(m)
pushed += 1
return None, math.inf, {"expanded": expanded, "pushed": pushed, "path_len": 0}
if __name__ == "__main__":
# 예시 격자: 0=통과, 1=장애물
grid = [
[0,0,0,0,0,0],
[0,1,1,1,0,0],
[0,0,0,1,0,0],
[0,1,0,0,0,0],
[0,0,0,0,1,0],
]
start, goal = (0,0), (4,5)
path, cost, stats = astar(grid, start, goal, diag=True, heuristic="auto", w=1.0)
print("경로:", path)
print("총 비용:", round(cost, 3))
print("통계:", stats)허용·일관 휴리스틱을 사용하면 w=1.0에서 최적성이 보장된다. 실시간 요구가 있을 때는 w를 1.2~1.5 범위로 조정해 속도와 품질의 균형을 맞출 수 있다. 대규모 맵에서는 장애물 희소성과 대칭성에 따라 JPS, ALT, 계층 그래프 사전처리를 적용한다.
탐색 성격으로 보는 알고리즘 선택
| 알고리즘 | 최적성 | 평가함수/휴리스틱 | 탐색 지향성 | 성능/확장성 | 운영 편의 |
|---|---|---|---|---|---|
| BFS | 비가중 그래프에서만 최단 보장 | 거리만 고려, 휴리스틱 없음 | 무작위적 레벨 확장 | 대규모에서 비효율 | 구현 용이 |
| Dijkstra | 가중 그래프 최단 보장 | g만 사용, h=0 | 전체적으로 균등 탐색 | 확장 수 큼 | 안정적이지만 느림 |
| Greedy Best-First | 비최적 가능 | h만 사용, g=0 | 목표 지향 강함 | 빠르나 품질 불안정 | 간단 |
| A* | 허용·일관 h에서 최적 보장 | f=g+h | 목표 지향+비용 인지 균형 | 실무 표준 수준의 효율 | 휴리스틱 설계 중요 |
A의 장점은 목표 쪽으로 탐색을 유도하면서도 누적 비용을 놓치지 않는 데 있다. 허용·일관 휴리스틱, 비음수 비용, 우선순위 큐 기반 상태 관리를 지키면 최적성·완전성·성능을 함께 다룰 수 있다. 네비게이션, 게임, 로보틱스에서는 요구되는 실시간성과 맵 특성에 따라 Weighted A, JPS, ALT를 선택한다.