Quick Flow
목표가 하나이고 남은 비용을 과대평가하지 않는 추정치 h를 만들 수 있으면 A*를 고릅니다. g는 이미 든 비용, h는 목표까지의 하한, 우선순위 f = g + h는 둘의 합입니다. 모든 간선 비용은 0 이상이어야 합니다.
static long Priority(long costSoFar, long estimatedRemainingCost)
{
return checked(costSoFar + estimatedRemainingCost); // f = g + h
}
// h가 항상 실제 남은 최단 비용 이하라면 최단 경로를 보장합니다.
// h를 0으로 두면 A*는 다익스트라와 같은 선택을 합니다.- 격자의 상하좌우 이동과 동일 비용: Manhattan distance
- 대각선 이동과 동일 비용: Chebyshev distance 또는 이동 규칙에 맞춘 거리
- 신뢰할 수 있는 하한이 없음:
h = 0으로 두거나 다익스트라
구조
A*는 다익스트라처럼 가장 유망한 후보를 우선순위 큐에서 꺼냅니다. 차이는 현재까지의 실제 비용 g만 보지 않고, 목표까지 가까워 보이는 정도 h를 더한다는 점입니다. h는 남은 비용의 하한이어야 하며, 실제 비용보다 큰 추정치를 넣으면 빠르게 도착하더라도 최단 경로가 아닐 수 있습니다.
f = g + h
g: 시작점에서 현재 정점까지 찾은 최선 비용
h: 현재 정점에서 목표까지의 실제 비용 이하인 추정치격자에서 상하좌우로만 움직이고 이동 비용이 모두 1이면 Manhattan distance가 이동 횟수의 하한입니다. 벽은 경로를 돌아가게 만들 수 있지만 거리를 짧게 만들지는 않으므로 이 조건을 만족합니다.
readonly record struct Point(int X, int Y);
static long Manhattan(Point a, Point b)
{
return Math.Abs((long)a.X - b.X) + Math.Abs((long)a.Y - b.Y);
}휴리스틱이 모든 간선 current -> next에 대해 h(current) <= cost(current, next) + h(next)를 만족하면 일관적(consistent)입니다. 이 조건에서는 경로를 따라 f = g + h가 줄어들지 않으므로, 정점을 처음 확정할 때 닫아도 안전합니다. 아래 구현은 닫힌 집합으로 고정하지 않고 더 좋은 g를 다시 넣으므로, admissible한 휴리스틱이지만 일관적이지 않은 경우도 재개방할 수 있습니다.
우선순위 큐는 항목 하나의 우선순위를 직접 낮추지 않습니다. 더 좋은 g를 찾을 때 새 항목을 넣고, 꺼낼 때 저장된 최선 g와 다르면 오래된 항목으로 버립니다. 이 방식은 일관되지 않은 휴리스틱에서 더 좋은 경로가 발견됐을 때도 정점을 다시 열 수 있습니다.
static List<Point> FindPath(
IReadOnlyDictionary<Point, IReadOnlyList<(Point To, long Cost)>> graph,
Point start,
Point goal)
{
var open = new PriorityQueue<(Point Node, long Cost), long>();
var bestCost = new Dictionary<Point, long> { [start] = 0 };
var previous = new Dictionary<Point, Point>();
open.Enqueue((start, 0), Manhattan(start, goal));
while (open.TryDequeue(out var candidate, out _))
{
Point current = candidate.Node;
if (candidate.Cost != bestCost[current]) continue;
if (current == goal) return RestorePath(previous, start, goal);
if (!graph.TryGetValue(current, out IReadOnlyList<(Point To, long Cost)>? edges)) continue;
foreach ((Point next, long edgeCost) in edges)
{
if (edgeCost < 0) throw new ArgumentOutOfRangeException(nameof(graph));
long nextCost = checked(candidate.Cost + edgeCost);
if (bestCost.TryGetValue(next, out long knownCost) && nextCost >= knownCost) continue;
bestCost[next] = nextCost;
previous[next] = current;
open.Enqueue((next, nextCost), Priority(nextCost, Manhattan(next, goal)));
}
}
return [];
}
static List<Point> RestorePath(
IReadOnlyDictionary<Point, Point> previous,
Point start,
Point goal)
{
var path = new List<Point>();
for (Point current = goal; current != start; current = previous[current]) path.Add(current);
path.Add(start);
path.Reverse();
return path;
}선택 기준
| 문제 조건 | 선택 |
|---|---|
| 간선 비용이 모두 1이고 전체 최단 거리 필요 | BFS |
| 목표가 하나이고 방향 감각이 있음 | A* |
| 휴리스틱이 없거나 부정확함 | 다익스트라 |
| 음수 간선이 있음 | Bellman-Ford |
| 모든 정점 쌍 거리 필요 | Floyd-Warshall |
A*는 목표가 명확할 때 탐색 범위를 줄이는 데 강합니다. 반대로 모든 정점까지의 거리가 필요하거나 목표 방향을 예측하기 어려우면 다익스트라와 큰 차이가 없을 수 있습니다. 휴리스틱이 과소평가이지만 정보가 적으면 정답은 유지해도 불필요한 후보가 늘고, 과대평가하면 최단 경로 보장이 깨집니다.
주의할 점
휴리스틱이 실제 남은 최단 비용보다 커지면 최단 경로 보장이 깨질 수 있습니다. 최단 경로가 반드시 필요하면 과대평가하지 않는 휴리스틱을 사용해야 합니다. 대각선 이동을 허용하는데 Manhattan distance를 그대로 쓰는 식으로 이동 규칙과 휴리스틱을 섞으면 이 경계가 쉽게 깨집니다.
우선순위 큐에 같은 정점이 여러 번 들어갈 수 있습니다. 단순 closed 집합에 처음 꺼낸 정점을 고정하면 더 좋은 경로를 놓칠 수 있습니다. 위처럼 현재 꺼낸 비용이 저장된 최선 비용과 같은지 확인하고, 더 좋은 경로는 다시 넣는 방식이 안전합니다.
참고 링크
2 sources