A* 탐색 체험

인공지능 기초 · 인공지능의 이해 — A* 탐색은 "지금까지 온 거리(g)"와 "목표까지 남은 거리 추정치(h, 휴리스틱)"를 더한 값 f = g + h가 가장 작은 칸부터 확장한다. 맨해튼 거리를 휴리스틱으로 써서 한 단계씩 진행해 보자.

1. 한 단계씩 진행하기

아래 8×8 맵에서 초록(S)=시작, 분홍(G)=목표, 회색=장벽. "한 단계 진행"을 눌러 f값이 가장 작은 칸부터 열리는 과정을 확인하세요.

열린 목록(open)

–

닫힌 목록(closed)

–

현재 확장 칸의 f값

–

상태

대기

「한 단계 진행」을 눌러 A* 탐색을 시작하세요.

기호	의미
g(n)	시작 지점에서 현재 칸 n까지 실제로 이동한 거리
h(n)	현재 칸 n에서 목표까지 남은 거리의 «추정치» (여기서는 맨해튼 거리)
f(n) = g(n) + h(n)	이 값이 가장 작은 칸을 다음에 확장한다

A*가 좋은 이유 — 그리디 탐색은 h만 보고 판단해 최단경로를 놓칠 수 있지만, A*는 «지금까지 온 거리(g)»도 함께 고려하기 때문에 휴리스틱이 목표까지 거리를 과대평가하지 않는 한 항상 최단경로를 찾아낸다는 것이 증명되어 있다.

한 줄 요약 — A*는 «이미 온 거리»와 «남은 거리 추정»을 더한 f값이 가장 작은 칸부터 확장해, 정보이용 탐색이면서도 최단경로를 보장한다.

관련: 맹목적 탐색 vs 정보이용 탐색 · 탐색 문제 설계 체험