안녕하세요. 자바파커입니다.

다익스트라 알고리즘은 최단 경로를 정확하게 찾습니다. 다만 목적지가 오른쪽 위에 있어도 시작점 주변을 모든 방향으로 넓게 확인합니다.

A*는 여기에 질문 하나를 더합니다.

지금까지 싸게 왔고, 목적지에도 가까운 후보는 어디일까?

이번 예제에서 두 알고리즘이 찾은 경로 비용은 모두 22입니다. 하지만 확정한 칸은 다익스트라 165개, A* 26개였습니다. 같은 답을 찾으면서 탐색 범위만 목적지 방향으로 좁힌 것입니다.

A*의 점수 — f(n) = g(n) + h(n)

A*는 우선순위 큐에서 f(n)이 가장 작은 노드를 먼저 꺼냅니다.

f(n) = g(n) + h(n)

g(n): 시작점에서 n까지 실제로 이동한 비용
h(n): n에서 목적지까지 남았다고 추정한 비용

g(n)만 사용하면 다익스트라 알고리즘과 같습니다. h(n)이 목적지 방향을 알려주는 나침반 역할을 합니다.

격자에서 상하좌우로만 이동하고 한 칸 비용이 1이라면 맨해튼 거리를 자주 사용합니다.

function manhattan([x1, y1], [x2, y2]) {
  return Math.abs(x1 - x2) + Math.abs(y1 - y2)
}

대각선 이동이 가능하면 유클리드 거리나 옥타일 거리가 더 자연스러울 수 있습니다. 중요한 건 지도에서 허용하는 이동 규칙과 휴리스틱이 맞아야 한다는 점입니다.

다익스트라와 무엇이 다른가

두 알고리즘의 뼈대는 거의 같습니다.

A*가 언제나 시간 복잡도 자체를 낮추는 것은 아닙니다. 휴리스틱이 도움이 되지 않거나 장애물이 복잡하면 다익스트라처럼 많은 노드를 볼 수 있습니다. 강점은 목적지에 대한 문제 지식을 탐색 순서에 반영할 수 있다는 것입니다.

휴리스틱이 지켜야 하는 조건

최단 경로를 보장하려면 일반적으로 허용 가능성(admissibility) 이 필요합니다.

h(n) ≤ n에서 목적지까지의 실제 최소 비용

휴리스틱이 실제 비용보다 크게 추정하면 짧은 경로를 비싸다고 오해해 후보에서 밀어낼 수 있습니다.

그래프 탐색 구현에서는 일관성(consistency) 도 중요합니다.

h(n) ≤ cost(n, next) + h(next)

일관된 휴리스틱은 경로를 한 칸 이동했을 때 예상값이 갑자기 비정상적으로 줄어들지 않게 합니다. 구현에 따라 일관성이 없으면 이미 닫은 노드를 다시 여는 처리가 필요할 수 있습니다.

JavaScript 구현

아래 코드는 설명을 위해 배열 정렬로 우선순위 큐를 단순화했습니다. 큰 그래프에서는 이진 힙을 사용해야 합니다.

function aStar(graph, start, goal, heuristic) {
  const open = [[heuristic(start, goal), 0, start]]
  const gScore = new Map([[start, 0]])
  const previous = new Map()

  while (open.length) {
    open.sort((a, b) => a[0] - b[0])
    const [, cost, current] = open.shift()

    if (cost !== gScore.get(current)) continue
    if (current === goal) return restorePath(previous, goal)

    for (const [next, weight] of graph.get(current) ?? []) {
      const nextCost = cost + weight

      if (nextCost < (gScore.get(next) ?? Infinity)) {
        gScore.set(next, nextCost)
        previous.set(next, current)
        open.push([nextCost + heuristic(next, goal), nextCost, next])
      }
    }
  }

  return null
}

function restorePath(previous, goal) {
  const path = []
  for (let at = goal; at !== undefined; at = previous.get(at)) path.push(at)
  return path.reverse()
}

실무에서는 오래된 큐 항목 무시, 최소 힙, 경로 없음 처리, 동적 장애물과 교통 비용까지 함께 고려해야 합니다.

지도 앱은 A* 하나만 사용할까

실제 도로망은 단순한 격자가 아닙니다. 거리뿐 아니라 속도, 신호, 통행 제한, 시간대별 교통량도 비용에 들어갑니다.

대규모 지도 서비스에서는 A* 외에도 양방향 탐색, 계층형 경로 탐색, 전처리된 지름길, 실시간 교통 업데이트를 함께 사용합니다. A*는 그중 “목적지 방향으로 탐색을 유도한다”는 핵심 아이디어를 가장 명확하게 보여주는 알고리즘입니다.

HNSW 벡터 검색도 모든 후보를 비교하지 않고 가까울 가능성이 높은 방향부터 이동합니다. 다만 HNSW는 근사 최근접 탐색이고 A*는 조건을 만족하는 휴리스틱에서 최단 경로를 보장한다는 차이가 있습니다.

정리

1. 다익스트라는 지금까지의 실제 비용 g(n)이 작은 노드부터 봅니다.
2. A*는 남은 예상 비용 h(n)을 더해 목적지 방향을 우선합니다.
3. h(n)=0이면 A*는 다익스트라와 같아집니다.
4. 휴리스틱은 실제 남은 비용을 과대평가하지 않아야 합니다.
5. 좋은 휴리스틱은 답을 바꾸지 않고 탐색 범위를 줄입니다.

A*의 핵심은 더 좋은 길을 찍는 것이 아니라, 볼 필요가 적은 곳을 알려주는 것입니다.

자주 묻는 질문 (FAQ)

A*는 항상 다익스트라보다 빠른가요?

아닙니다. 휴리스틱 계산 비용이 크거나 목적지 방향을 잘 알려주지 못하면 이점이 작습니다. 최악의 경우 다익스트라와 비슷한 범위를 탐색할 수 있습니다.

h(n)을 크게 잡으면 목적지에 더 빨리 가지 않나요?

탐색은 더 공격적으로 좁아질 수 있지만 최단 경로 보장을 잃을 수 있습니다. 정확성이 필요하다면 실제 남은 최소 비용을 넘지 않는 휴리스틱을 사용해야 합니다.

A*는 음수 가중치를 처리할 수 있나요?

일반적인 A* 구현은 비음수 가중치를 전제로 합니다. 음수 가중치가 있으면 다익스트라와 같은 전제가 깨지므로 Bellman–Ford 같은 다른 알고리즘을 검토해야 합니다.

맨해튼 거리는 언제 사용하나요?

격자에서 상하좌우로만 움직이고 이동 비용이 한 칸당 동일할 때 적합합니다. 대각선이나 서로 다른 지형 비용을 허용한다면 이동 규칙에 맞는 다른 휴리스틱이 필요합니다.

참고 자료

• Hart, Nilsson, Raphael — A Formal Basis for the Heuristic Determination of Minimum Cost Paths
• NetworkX — astar_path
• Boost.Graph — A* Heuristic Search