핵심 정리
| 기준 | 내용 |
|---|---|
| 우선순위 | f(n) = g(n) + h(n) |
g(n) | 시작점에서 현재 정점까지의 실제 비용 |
h(n) | 현재 정점에서 목표까지의 추정 비용 |
| 보장 조건 | 휴리스틱이 실제 남은 비용을 넘지 않음 |
| 결과 | 단일 목표까지의 최단 경로 |
csharp
var open = new PriorityQueue<Point, int>();
dist[start] = 0;
open.Enqueue(start, Heuristic(start, goal));구조
A*는 다익스트라처럼 가장 유망한 후보를 우선순위 큐에서 꺼냅니다. 차이는 현재까지의 실제 비용만 보지 않고, 목표까지 가까워 보이는 정도를 함께 반영한다는 점입니다.
text
f = g + h
g: 이미 확정한 이동 비용
h: 목표까지 남았다고 추정한 비용격자에서 상하좌우만 이동하고 모든 이동 비용이 1이라면 Manhattan distance를 휴리스틱으로 자주 씁니다.
csharp
int Heuristic(Point a, Point b)
{
return Math.Abs(a.X - b.X) + Math.Abs(a.Y - b.Y);
}탐색 루프는 다익스트라와 비슷합니다. 더 짧은 g를 찾았을 때만 거리와 이전 위치를 갱신하고, 우선순위는 새 g + h로 넣습니다.
csharp
while (open.Count > 0)
{
Point current = open.Dequeue();
if (current == goal) break;
foreach (Point next in Neighbors(current))
{
int nextCost = dist[current] + Cost(current, next);
if (nextCost >= dist[next]) continue;
dist[next] = nextCost;
prev[next] = current;
open.Enqueue(next, nextCost + Heuristic(next, goal));
}
}선택 기준
| 문제 조건 | 선택 |
|---|---|
| 간선 비용이 모두 1이고 전체 최단 거리 필요 | BFS |
| 목표가 하나이고 방향 감각이 있음 | A* |
| 휴리스틱이 없거나 부정확함 | 다익스트라 |
| 음수 간선이 있음 | Bellman-Ford |
| 모든 정점 쌍 거리 필요 | Floyd-Warshall |
A*는 목표가 명확할 때 탐색 범위를 줄이는 데 강합니다. 반대로 모든 정점까지의 거리가 필요하거나 목표 방향을 예측하기 어려우면 다익스트라와 큰 차이가 없을 수 있습니다.
주의할 점
휴리스틱이 실제 남은 최단 비용보다 커지면 최단 경로 보장이 깨질 수 있습니다. 최단 경로가 반드시 필요하면 과대평가하지 않는 휴리스틱을 사용해야 합니다.
우선순위 큐에 같은 정점이 여러 번 들어갈 수 있습니다. 현재 꺼낸 비용이 저장된 dist와 맞는지 확인하거나, 방문 처리 시점이 최단 경로 보장을 해치지 않는지 따져야 합니다.