A* 알고리즘

A* 알고리즘(A-star algorithm, 에이스타 알고리즘)은 그래프 탐색의 한 종류로, 주어진 출발점에서 목표점까지의 최단 경로를 찾아내는 알고리즘이다. 최상의 경로를 우선적으로 탐색하는 최선 우선 탐색에, 출발점부터 현재 위치까지의 비용(g)과 현재 위치부터 목표점까지의 추정 비용(h, 휴리스틱)을 더한 값을 평가 기준으로 사용하는 것이 특징이다.

1968년 피터 하트(Peter Hart), 닐스 닐슨(Nils Nilsson), 버트램 라팰(Bertram Raphael)에 의해 처음 발표되었다. 적절한 휴리스틱 함수를 사용할 경우, 최적의 해를 찾는 것을 보장하면서도 다익스트라 알고리즘보다 빠른 속도를 보인다. 주로 비디오 게임의 유닛 길찾기나 내비게이션 시스템 등에서 널리 활용된다.

개요

A* 알고리즘은 각 노드 n에 대해 다음 평가 함수 f(n)을 계산하여 경로 탐색의 우선순위를 정한다.

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

g(n): 출발점으로부터 현재 노드 n까지 이동하는 데 소요된 실제 비용.
h(n): 현재 노드 n으로부터 목표점까지의 예상 비용. 이 값을 추정하는 함수를 '휴리스틱 함수'라고 한다.
f(n): 출발점에서 노드 n을 거쳐 목표점까지 가는 데 드는 총 예상 비용.

알고리즘은 '열린 목록(Open List)'과 '닫힌 목록(Closed List)'이라는 두 개의 목록을 유지한다. 열린 목록에는 앞으로 탐색할 노드들이, 닫힌 목록에는 이미 탐색이 완료된 노드들이 저장된다. 알고리즘은 열린 목록에서 f(n) 값이 가장 작은 노드를 선택하여 탐색을 진행한다. 이 과정을 목표점에 도달할 때까지 반복한다.

알고리즘의 동작 원리

초기화: 열린 목록에 출발점을 추가하고, 출발점의 g(n) 값은 0, f(n) 값은 휴리스틱 함수로 계산된 h(n) 값으로 설정한다.
반복:
1. 열린 목록에서 f(n) 값이 가장 작은 노드를 선택하고, 이 노드를 현재 노드로 지정한 뒤 열린 목록에서 제거하고 닫힌 목록에 추가한다.
2. 만약 현재 노드가 목표점이라면, 부모 노드를 역추적하여 최종 경로를 구성하고 탐색을 종료한다.
3. 현재 노드에 인접한 각 노드에 대해 다음을 수행한다:
  1. 인접 노드가 닫힌 목록에 있거나 이동 불가능한 지역이라면 무시한다.
  2. 인접 노드가 열린 목록에 없다면, 해당 노드를 열린 목록에 추가한다. 이때 현재 노드를 부모 노드로 설정하고, g(n)과 f(n) 값을 계산한다.
  3. 인접 노드가 이미 열린 목록에 있다면, 현재 노드를 거쳐가는 경로가 기존 경로보다 더 효율적인지(g(n) 값이 더 작은지) 확인한다. 만약 더 효율적이라면 부모 노드와 g(n), f(n) 값을 갱신한다.
만약 열린 목록이 비게 되면, 이는 목표점까지의 경로가 존재하지 않음을 의미한다.

최적화

실제 구현에서는 명시적인 닫힌 목록(Closed List)을 별도로 관리하지 않고, 각 노드까지의 최소 비용을 저장하는 `cost_so_far` (또는 `g_score`) 자료구조를 활용하여 효율을 높이는 방식이 자주 사용된다.

명시적 닫힌 목록 제외 방식

이 방식은 특정 노드에 도달했을 때의 비용을 해시 맵이나 딕셔너리에 저장하고, 새로운 경로를 통해 도달한 비용이 기존 기록보다 작을 때만 해당 노드를 업데이트하고 열린 목록(우선순위 큐)에 다시 삽입한다.

장점
- 엣지 비용 대응: 간선(Edge)의 비용이 일정하지 않은 그래프에서 이미 방문한 노드라도 더 짧은 경로가 발견되면 유연하게 경로를 갱신할 수 있어 최적성을 보장하기 쉽다.
- 구현의 간결성: 방문 여부 확인과 비용 관리를 하나의 자료구조로 통합할 수 있어 코드가 단순해진다.
단점
- 우선순위 큐 중복: 동일한 노드가 서로 다른 비용으로 우선순위 큐에 여러 번 들어갈 수 있어, 큐의 크기가 커지고 처리 오버헤드가 발생할 수 있다.
- 메모리 사용: 모든 방문 후보 노드의 비용 정보를 유지해야 하므로 단순 세트(Set) 기반의 닫힌 목록보다 메모리 점유율이 높을 수 있다.

의사코드

frontier = PriorityQueue()
frontier.put(start, 0)
came_from = dict()
cost_so_far = dict()
came_from[start] = None
cost_so_far[start] = 0

while not frontier.empty():
    current = frontier.get()

    if current == goal:
        break
    
    for next in graph.neighbors(current):
        new_cost = cost_so_far[current] + graph.cost(current, next)
        if next not in cost_so_far or new_cost < cost_so_far[next]:
            cost_so_far[next] = new_cost
            priority = new_cost + heuristic(goal, next)
            frontier.put(next, priority)
            came_from[next] = current

휴리스틱 함수 (Heuristic Function)

휴리스틱 함수의 성능은 A* 알고리즘의 전체 효율성에 직접적인 영향을 미친다. 좋은 휴리스틱 함수는 목표점까지의 실제 거리보다 항상 작거나 같은 값을 반환해야 한다. 이를 '허용 가능한(admissible) 휴리스틱'이라고 하며, 이 조건이 만족될 때 A*는 최단 경로를 보장한다.

맨해튼 거리 (Manhattan Distance): 격자 형태의 맵에서 상하좌우로만 이동할 수 있을 때 주로 사용된다.
유클리드 거리 (Euclidean Distance): 두 점 사이의 직선 거리로, 모든 방향으로 이동이 가능할 때 유용하다.
대각선 거리 (Diagonal Distance): 격자 맵에서 대각선 이동이 허용될 때 사용된다.

특징

완전성 (Completeness): 해가 존재하는 한 반드시 찾아낸다.
최적성 (Optimality): 허용 가능한 휴리스틱 함수를 사용하면, 항상 최단 경로를 찾아낸다.
효율성 (Efficiency): 동일한 휴리스틱을 사용하는 다른 최적 알고리즘에 비해 가장 적은 수의 노드를 탐색한다.

응용 분야

게임 개발: NPC나 캐릭터의 길찾기(Pathfinding) AI에 핵심적으로 사용된다.
로보틱스 및 내비게이션: 로봇의 자율 주행 및 최적 경로 계획에 활용된다.
네트워크 라우팅: 데이터 패킷의 최적 전송 경로를 결정하는 데 사용될 수 있다.
인공지능 문제 해결: 8-퍼즐과 같은 다양한 탐색 문제의 해를 구하는 데 적용된다.

같이 보기

참고