A* 알고리즘(A-star Algorithm)

개요

A* 알고리즘(A-star)은 그래프 상에서 출발 지점부터 목표 지점까지의 최적 경로를 효율적으로 탐색하기 위한 알고리즘으로, 실제 경로 비용(g)과 목적지까지의 추정 비용(h)을 합산하여 우선순위를 판단하는 휴리스틱 기반 최단 경로 탐색 알고리즘이다. 경로의 정확성과 탐색 속도 간의 균형을 이뤄, 게임 개발, 로봇 경로 계획, 내비게이션 등에서 널리 사용된다.

---

1. 개념 및 정의

A* 알고리즘은 다음 공식을 기준으로 노드의 우선순위를 평가한다:

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

• g(n): 시작 노드에서 현재 노드까지의 실제 거리(비용)
• h(n): 현재 노드에서 목표 노드까지의 휴리스틱(예상 비용)
• f(n): 현재 노드를 지나 목표까지의 전체 추정 비용

이렇게 계산된 f(n)이 가장 작은 노드를 우선적으로 탐색한다.

---

2. A* 알고리즘의 핵심 요소

요소	설명
Open List	아직 방문하지 않은 후보 노드 (우선순위 큐)
Closed List	이미 방문한 노드 집합
휴리스틱 함수	맨해튼 거리, 유클리드 거리 등
경로 추적	부모 노드를 저장하여 최단 경로 재구성 가능

적절한 휴리스틱 함수는 A* 알고리즘의 성능을 결정짓는 핵심이다.

---

3. 파이썬 간단 구현 예시 (우선순위 큐 기반)

import heapq

def a_star(start, goal, graph, heuristic):
    open_list = [(0 + heuristic[start], 0, start, [])]  # f, g, node, path
    visited = set()

    while open_list:
        f, g, current, path = heapq.heappop(open_list)
        if current in visited:
            continue
        visited.add(current)
        path = path + [current]

        if current == goal:
            return path

        for neighbor, cost in graph[current]:
            heapq.heappush(open_list, (g + cost + heuristic[neighbor], g + cost, neighbor, path))
    return None

이 구현은 간결하고 직관적으로 A*의 핵심 흐름을 표현한다.

---

4. 휴리스틱 함수의 종류

함수명	적용 예시	설명
맨해튼 거리	격자형 맵	∣x1​−x2​∣+∣y1​−y2​∣
유클리드 거리	자유 공간	sqrt((x1 - x2)² + (y1 - y2)²)
체비셰프 거리	대각선 이동 가능	max(∣x1​−x2​∣,∣y1​−y2​∣)

휴리스틱 함수가 정확할수록 탐색 효율이 높아지며, 과소 추정해야 최적성이 보장된다.

---

5. 시간 및 공간 복잡도

항목	복잡도
시간 복잡도	O(E) (E: 간선 수, 휴리스틱에 따라 달라짐)
공간 복잡도	O(V) (V: 노드 수)

최악의 경우 BFS 수준이 될 수 있으나, 평균적으로 매우 빠름.

---

6. A* vs 다익스트라 vs BFS 비교

항목	A*	다익스트라	BFS
휴리스틱 사용	O	X	X
최단 경로 보장	O (h가 admissible)	O	O (무가중치)
탐색 효율	매우 높음	보통	낮음
구현 복잡도	중	중	낮음

A*는 휴리스틱으로 인해 실제 환경에서 가장 빠르고 효율적이다.

---

7. 활용 사례

분야	활용 예시
게임 개발	NPC 경로 탐색, 실시간 AI 네비게이션
로봇 제어	장애물 회피 기반 경로 계획
물류/배송	물류창고 경로 최적화, 드론 경로 설정
GIS 시스템	지도 기반 길찾기, 내비게이션 경로 분석
알고리즘 문제풀이	시간 최소 경로 탐색, 제한 조건 있는 경로 탐색

A*는 휴리스틱이 중요한 모든 탐색 문제에서 가장 널리 사용된다.

---

8. 결론

A* 알고리즘은 실제 거리와 휴리스틱을 조합해 최단 경로를 효율적으로 찾는 탐색 알고리즘으로, 다익스트라보다 빠르고, BFS보다 정확하다. 다양한 휴리스틱과 결합해 유연하게 사용할 수 있으며, 게임, 로봇, 지도, 물류 등 수많은 분야에서 그 효용성을 입증받고 있다. 실전형 알고리즘을 공부하는 개발자라면 반드시 이해하고 구현할 줄 알아야 할 핵심 알고리즘이다.