A* 탐색
방향 감각이 있는 다익스트라입니다. 각 장소의 비용에 남은 비용의 추정치를 더하므로, 목표에 가장 가까워 보이는 곳부터 시도합니다.
- 시간 O((V + E) log V)
- 메모리 O(V)
- 우선순위 큐 사용
용어 설명
- 비용: 한 번 이동하는 값. 미로에서는 땅 1, 진흙 3, 물 9이고, 그래프에서는 간선에 적힌 수입니다.
- 우선순위 큐: 먼저 온 순서가 아니라 가장 싼 것이 먼저 나가는 대기열.
- 추정치(h): 남은 비용에 대한 예상. 추정치가 결코 너무 크지 않을 때만 A*가 정확합니다.
- 간선 완화: 현재 장소를 거치면 이웃의 비용이 낮아지는지 확인하고, 낮아지면 그 값을 받아들이는 것.
0 / 205 단계
- 큐에 있음
- 현재
- 완료
- 가장 싼 길
- 땅 · 1
- 진흙 · 3
- 물 · 9
- 벽
발견: A1에서 비용 0, 목표까지 추정치 26로 시작합니다. 큐에 있는 유일한 칸입니다.
스페이스바: 재생 또는 일시정지. 좌우 화살표 키: 단계 이동. Home과 End 키: 처음과 끝으로 이동.
해 보세요: ‘열린 들판’을 고르고 다익스트라와 A*를 번갈아 보세요. 둘 다 같은 비용의 길을 찾지만, A*가 큐에서 꺼내는 칸은 훨씬 적습니다.
작동 방식
A*는 다익스트라처럼 동작하지만 큐를 f = 지금까지의 비용 + h 순으로 정렬합니다. h는 남은 비용의 추정치입니다. 미로에서는 벽과 진흙을 무시한 M까지의 이동 수, 그래프에서는 직선거리를 10으로 나눈 값입니다. h가 절대 과대평가하지 않는 한, 목표를 꺼낼 때 A*가 가진 길은 다익스트라와 똑같이 가장 싼 길입니다. 추정이 좋을수록 살펴볼 곳이 줄어듭니다.
언제 쓰면 좋을까
목표가 하나이고 그 거리를 추정할 수 있을 때 쓰세요. 게임의 경로 찾기, 로봇, 지도의 경로 안내 등입니다. h = 0이면 정확히 다익스트라입니다. 과대평가할 수 있는 추정치는 A*를 빠르게 하지만 가장 싼 길을 놓칠 수 있습니다.