Algorithm Guidecomplexity: O(E)

A* 탐색 (A-Star Search)

f(n) = g(n) + h(n) 이 가장 작은 노드를 우선 확장하는 휴리스틱 기반 최단 경로 알고리즘입니다. 휴리스틱이 admissible 하면 최적 경로를 보장하며, 경로 탐색·게임 AI·로봇 내비게이션의 표준 도구입니다.

01A* 탐색 (A-Star Search)

알고리즘 작동 원리 탐색

A* 탐색 시작. f(n)=g(n)+h(n)이 가장 작은 노드부터 확장하며, 휴리스틱이 실제 비용을 넘지 않으면 최적 경로를 보장합니다.

open set에서 f가 가장 작은 A(f=10)를 꺼내 확장합니다. 이웃 B, C의 g·f 값을 계산합니다.

B까지 실제로 든 비용은 1, 남은 거리 어림값은 8 — 합쳐 f=9로 두고 open set에 넣습니다.

C는 실제 비용 3에 어림값 5를 더해 f=8. B의 9보다 작아 먼저 살펴볼 후보가 됩니다.

f가 가장 작은 C(f=8)를 꺼내 확장합니다. B(f=9)보다 먼저 선택되는 것 — 이것이 A*가 Dijkstra보다 빠른 이유입니다.

D는 실제 비용 4에 어림값 3을 더해 f=7. 지금까지 중 가장 유망한 길입니다.

f가 가장 작은 D(f=7)를 꺼내 확장합니다.

G는 실제 비용 5에 어림값 0 — 목표에 닿았으니 f도 5입니다.

G(f=5)를 꺼내 목표와 일치 — 최적 경로 A → C → D → G (비용 5). B는 가지치기되어 확장되지 않습니다.

탐색 완료 · 최적 경로 A → C → D → G (비용 5). 휴리스틱이 탐색 방향을 효과적으로 이끈 결과입니다.

Live Python

1def a_star(graph, start, goal, h):

# open = [(A, 10)]

2 open_set = [(h[start], start)] # min-heap by f

3 g = {start: 0}

# g[A] = 0

4 parent = {start: None}

5 closed = set()

6 while open_set:

7 f_cur, current = heappop(open_set)

8 if current == goal:

9 return reconstruct(parent, goal)

10 closed.add(current)

11 for nb, w in graph[current]:

12 if nb in closed:

13 continue

14 tentative = g[current] + w

15 if tentative < g.get(nb, INF):

16 g[nb] = tentative

17 parent[nb] = current

18 heappush(open_set,

19 (tentative + h[nb], nb))

20 return None

1 / 10

02 쉽게 이해하기

For Everyone

🔑핵심 동작

지금까지의 비용 g 에 남은 거리의 어림값 h 를 더한 f 가 작은 것부터 봅니다. h 가 실제 비용을 넘지 않으면 최단 경로를 보장합니다.

💡쉽게 말하면

실제 비용 g와 목적지까지의 추정 h를 더한 f가 작은 노드부터 확장합니다.

좋은 추정이면 다익스트라보다 빨라요.

📍어디에 쓰나

–게임 길찾기
–로봇 내비게이션
–경로 탐색

03 파이썬 구현 코드

A* 탐색 (A-Star Search)의 핵심 로직을 담은 표준 구현 예시입니다. 가급적 간결하고 읽기 쉬운 코드로 작성되었습니다.

core_implementation.py

from heapq import heappush, heappop

def a_star(graph, start, goal, h):
    open_set = [(h[start], start)]
    g = {start: 0}
    parent = {start: None}
    closed = set()
    while open_set:
        f_cur, current = heappop(open_set)
        if current == goal:
            return reconstruct(parent, goal)
        closed.add(current)
        for nb, w in graph[current]:
            if nb in closed:
                continue
            tentative = g[current] + w
            if tentative < g.get(nb, float("inf")):
                g[nb] = tentative
                parent[nb] = current
                heappush(open_set,
                         (tentative + h[nb], nb))
    return None