A* 길찾기
목적지를 아는 탐색
A*
A*(에이스타)는 시작점에서 목적지까지 최단 경로를 찾는 탐색 알고리즘이다. 너비 우선 탐색처럼 사방으로 균등하게 넓혀가는 대신, 목적지까지 남은 거리를 추정한 값을 함께 고려해서 훨씬 적은 칸만 살펴보고도 최단 경로를 찾아낸다.
비용 함수
A*는 매 칸마다 세 값을 계산하고 그중 f(n)이 가장 작은 칸부터 탐색한다.
| 값 | 의미 |
|---|---|
| g(n) | 시작점부터 n까지 실제로 이동한 거리 |
| h(n) | n부터 목적지까지 남은 거리를 추정한 값(휴리스틱) |
| f(n) | g(n) + h(n), n을 지나는 경로의 예상 총비용 |
h(n)이 실제 남은 거리보다 항상 작거나 같기만 하면(admissible heuristic) A*는 항상 최단 경로를 보장한다. 이 데모는 대각선 이동 없이 상하좌우로만 움직이므로, 두 칸 사이의 거리를 맨해튼 거리로 추정했다.
열린 목록과 닫힌 목록
아직 살펴보지 않았지만 갈 수 있는 칸은 열린 목록에, 이미 살펴본 칸은 닫힌 목록에 담는다. 매 단계마다 열린 목록에서 f(n)이 가장 작은 칸을 하나 꺼내 닫힌 목록으로 옮기고 그 이웃 칸들을 다시 열린 목록에 채워 넣는 과정을 목적지에 도착할 때까지 반복한다.
시각화
칸을 드래그해서 벽을 그리면 그때마다 시작점부터 도착점까지 새로 탐색한다.
열린 목록닫힌 목록경로