Algorithm Guidecomplexity: O(E)

A* 탐색 (A-Star Search)

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

01 알고리즘 작동 원리 탐색

Interactive Step-by-Step

TAP OR HOVER

A* Search

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

Logic Node1 / 10

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

02 쉽게 이해하기

For Everyone

🔑비유

목적지 방향을 어림짐작해 그쪽으로 가까운 길부터 우선 살피는 내비게이션.

💡쉽게 말하면

실제 비용 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

Guide Progress0%