2026-02-03 | 6 min read | 105 | 탐색 A* 알고리즘

4-8. 탐색 알고리즘: A* (A스타) 알고리즘

1. A* 알고리즘의 소개

A (A-star, 에이스타) 알고리즘은 그래프 탐색 및 최단 경로 탐색 문제에 널리 사용되는 알고리즘입니다. 특히 게임 개발, 로봇 공학, 인공지능 분야에서 효과적인 경로 계획을 위해 활용됩니다. 다익스트라(Dijkstra) 알고리즘과 유사하지만, A는 휴리스틱(Heuristic) 함수를 사용하여 탐색의 효율성을 높인다는 점에서 차별점을 가집니다. 즉, 목표 지점까지의 예상 거리를 추정하여 탐색 방향을 결정함으로써 불필요한 탐색을 줄여 최적의 경로를 빠르게 찾을 수 있도록 합니다.

A* 알고리즘은 주어진 시작 노드에서 목표 노드까지의 최단 경로를 찾는 데 목표를 둡니다. 이는 지도상의 두 지점 사이의 최단 거리를 찾는 것과 같은 문제를 해결하는 데 매우 유용합니다.

2. A* 알고리즘의 원리

A* 알고리즘은 기본적으로 그래프 탐색 알고리즘인 BFS(Breadth-First Search, 너비 우선 탐색)와 Dijkstra's Algorithm을 결합한 형태로 볼 수 있습니다. 각 노드에 대한 평가 함수 f(n)을 사용하여 탐색 우선순위를 결정합니다. 여기서 n은 그래프의 노드를 나타냅니다.

f(n)은 다음과 같이 정의됩니다.

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

g(n): 시작 노드에서 현재 노드 n까지의 실제 비용 (path cost).
h(n): 현재 노드 n에서 목표 노드까지의 예상 비용 (heuristic cost).

A* 알고리즘의 핵심은 h(n)의 설계에 달려 있습니다. h(n)은 목표 지점까지의 거리를 "추정"하는 함수로, 이 추정치가 얼마나 정확한가에 따라 알고리즘의 성능이 크게 달라집니다.

1) 휴리스틱 함수의 중요성

h(n)은 탐색의 효율성을 결정하는 중요한 요소입니다. 좋은 h(n) 함수는 다음과 같은 특징을 가져야 합니다.

Admissible (허용 가능성): h(n)은 실제 목표 노드까지의 비용보다 절대 크지 않아야 합니다. 즉, 과대평가하지 않아야 합니다. 과대평가하면 최단 경로를 보장하지 못할 수 있습니다.
Consistent (일관성): 노드 n에서 인접 노드 n'으로 이동하는 비용은 h(n)과 h(n')의 차이보다 작거나 같아야 합니다. 이는 삼각 부등식을 만족해야 함을 의미합니다. 일관성을 가지면 A* 알고리즘은 노드를 다시 방문할 필요가 없어 더욱 효율적입니다.

2) 휴리스틱 함수의 예시

h(n)의 예시는 문제의 특성에 따라 다양하게 정의될 수 있습니다.

유클리드 거리 (Euclidean Distance): 2차원 평면 상에서 두 점 사이의 직선 거리를 계산합니다.

$$ h(n) = \sqrt{(x_n - x_{goal})^2 + (y_n - y_{goal})^2} $$

맨해튼 거리 (Manhattan Distance): 격자 형태의 맵에서 수평 및 수직 이동만을 허용할 때 사용됩니다.

$$ h(n) = |x_n - x_{goal}| + |y_n - y_{goal}| $$

맨해튼 거리는 도시 블록과 같이 이동이 제한된 상황에서 유용합니다.

체스판 거리 (Chebyshev Distance): 체스판에서 킹의 이동처럼, 수평, 수직, 대각선 방향으로 이동이 가능한 경우 사용됩니다.

$$ h(n) = max(|x_n - x_{goal}|, |y_n - y_{goal}|) $$

3) A* 알고리즘의 작동 방식

초기화: 시작 노드를 OPEN 리스트에 추가하고, 각 노드의 g(n) 값을 무한대로 초기화합니다 (시작 노드는 0). f(n)은 g(n) + h(n)으로 계산합니다.
반복: OPEN 리스트가 빌 때까지 다음을 반복합니다.
- OPEN 리스트에서 f(n) 값이 가장 작은 노드 n을 선택합니다.
- 노드 n을 CLOSED 리스트로 옮깁니다.
- 노드 n의 이웃 노드 n'을 확인합니다.
 - n'이 CLOSED 리스트에 있으면 무시합니다.
 - n'이 OPEN 리스트에 없으면, g(n') g(n) + cost(n, n'), f(n') g(n') + h(n')을 계산하고 OPEN 리스트에 추가합니다.
 - n'이 OPEN 리스트에 있으면, g(n) + cost(n, n')가 기존 g(n')보다 작은지 확인합니다. 작으면 g(n')와 f(n')를 갱신합니다.
종료: 목표 노드가 CLOSED 리스트에 추가되면, 시작 노드에서 목표 노드까지의 최단 경로를 찾았습니다. CLOSED 리스트를 역추적하여 경로를 구성합니다.

3. A* 알고리즘의 구현

A* 알고리즘은 OPEN 리스트와 CLOSED 리스트를 사용하여 구현됩니다. OPEN 리스트는 아직 평가되지 않은 노드들을 저장하고, CLOSED 리스트는 이미 평가된 노드들을 저장합니다. 효율적인 구현을 위해 우선순위 큐(priority queue)를 사용하여 OPEN 리스트를 관리하는 것이 일반적입니다. 우선순위 큐는 f(n) 값이 가장 작은 노드를 빠르게 찾을 수 있도록 도와줍니다.

1) Python을 이용한 간단한 예제 (Grid Map)

다음은 간단한 2차원 그리드 맵에서 A* 알고리즘을 구현한 예제입니다.

import heapq

def a_star(grid, start, goal):
    """
    A* 알고리즘을 사용하여 그리드 맵에서 최단 경로를 찾습니다.

    Args:
        grid: 그리드 맵 (2차원 리스트, 0: 통행 가능, 1: 벽).
        start: 시작 노드 (tuple: (row, col)).
        goal: 목표 노드 (tuple: (row, col)).

    Returns:
        최단 경로 (list of tuples) 또는 경로가 없으면 None.
    """

    def heuristic(a, b):
        """
        맨해튼 거리 휴리스틱 함수.
        """
        return abs(a[0] - b[0]) + abs(a[1] - b[1])

    def get_neighbors(node):
        """
        주어진 노드의 이웃 노드를 반환합니다.
        """
        neighbors = []
        for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:  # 상하좌우
            nr, nc = node[0] + dr, node[1] + dc
            if 0 <= nr < len(grid) and 0 <= nc < len(grid[0]) and grid[nr][nc] == 0:
                neighbors.append((nr, nc))
        return neighbors

    # 초기화
    open_set = []  # (f_score, node) 형태로 저장
    heapq.heappush(open_set, (0, start))
    came_from = {}  # 경로를 추적하기 위한 딕셔너리
    g_score = {start: 0}  # 시작 노드에서 현재 노드까지의 비용
    f_score = {start: heuristic(start, goal)}  # 시작 노드에서 목표 노드까지의 예상 비용

    while open_set:
        current_f_score, current = heapq.heappop(open_set)

        if current == goal:
            # 경로 재구성
            path = []
            while current in came_from:
                path.append(current)
                current = came_from[current]
            path.append(start)
            return path[::-1]  # 경로를 역순으로 반환

        for neighbor in get_neighbors(current):
            # 현재 노드를 거쳐 이웃 노드로 가는 비용
            tentative_g_score = g_score[current] + 1  # grid에서 이동 비용은 1

            if neighbor not in g_score or tentative_g_score < g_score[neighbor]:
                # 이 경로가 더 좋음
                came_from[neighbor] = current
                g_score[neighbor] = tentative_g_score
                f_score[neighbor] = tentative_g_score + heuristic(neighbor, goal)
                if (neighbor not in [node for _, node in open_set]):
                    heapq.heappush(open_set, (f_score[neighbor], neighbor))

    return None  # 경로가 없으면 None 반환

# 예제 사용
grid = [
    [0, 0, 0, 0, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 1, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 0, 0]
]
start = (0, 0)
goal = (4, 4)
path = a_star(grid, start, goal)

if path:
    print("최단 경로:", path)
else:
    print("경로가 없습니다.")

2) 코드 설명

heuristic(a, b): 맨해튼 거리를 계산하여 휴리스틱 값을 반환합니다.
get_neighbors(node): 주어진 노드의 상하좌우 인접 노드를 반환합니다. 벽(1)은 제외합니다.
open_set: f_score와 노드를 튜플로 묶어 우선순위 큐로 사용합니다. heapq 모듈을 사용하여 구현됩니다.
came_from: 각 노드에 도달하기 위한 이전 노드를 저장하여 경로를 추적합니다.
g_score: 시작 노드에서 현재 노드까지의 비용을 저장합니다.
f_score: 시작 노드에서 목표 노드까지의 예상 비용을 저장합니다.

알고리즘은 OPEN 리스트에서 가장 낮은 f_score를 가진 노드를 선택하고, 해당 노드의 이웃 노드들을 탐색하며 g_score와 f_score를 업데이트합니다. 목표 노드에 도달하면 came_from을 사용하여 경로를 재구성합니다.

코드 예제 설명 뒤

4. A* 알고리즘의 응용 및 활용 사례

A* 알고리즘은 다양한 분야에서 활용됩니다.

게임 개발: 게임 캐릭터의 길 찾기, 적 AI의 이동 경로 설정, 맵 내비게이션 등에 사용됩니다.
로봇 공학: 로봇의 경로 계획, 자율 주행 차량의 경로 설정에 활용됩니다.
GIS (Geographic Information System) 및 지도 서비스: 지도에서 최단 경로를 찾는 데 사용됩니다.
라우팅 알고리즘: 네트워크 트래픽 최적화에 사용될 수 있습니다.

1) 게임 AI

게임 AI에서 A* 알고리즘은 적 캐릭터(NPC)가 플레이어를 쫓아가거나, 특정 지점으로 이동하도록 하는 데 사용됩니다. 맵의 복잡성과 장애물을 고려하여 효율적인 경로를 계산할 수 있습니다.

2) 자율 주행

자율 주행 시스템에서 A* 알고리즘은 차량이 장애물을 피하고 목적지까지 안전하게 이동할 수 있는 경로를 계획하는 데 사용됩니다. 차량의 센서 데이터, 맵 정보, 교통 상황 등을 고려하여 실시간으로 경로를 갱신할 수 있습니다.

5. A* 알고리즘의 장단점 및 주의사항

1) 장점

최적성 보장: 허용 가능한 휴리스틱 함수를 사용하면 최적의 경로를 찾을 수 있습니다.
효율성: 휴리스틱 함수를 통해 탐색 공간을 줄여 탐색 속도를 향상시킬 수 있습니다.
유연성: 다양한 문제에 맞게 휴리스틱 함수를 설계하여 적용할 수 있습니다.

2) 단점

휴리스틱 함수의 중요성: 휴리스틱 함수의 품질에 따라 성능이 크게 영향을 받습니다. 잘못된 휴리스틱 함수는 최적 경로를 보장하지 못하거나 탐색 속도를 저하시킬 수 있습니다.
메모리 사용량: OPEN 및 CLOSED 리스트에 많은 노드를 저장해야 하므로 메모리 사용량이 증가할 수 있습니다.
계산 복잡도: 최악의 경우, 모든 노드를 탐색해야 하므로 계산 복잡도가 증가할 수 있습니다.

3) 주의사항

휴리스틱 함수 선택: 문제의 특성에 맞는 적절한 휴리스틱 함수를 선택해야 합니다.
메모리 관리: 대규모 맵이나 복잡한 환경에서는 메모리 사용량을 고려하여 알고리즘을 구현해야 합니다.
성능 최적화: 휴리스틱 함수의 계산 시간을 줄이고, 우선순위 큐의 효율성을 높여 성능을 최적화해야 합니다.

6. 결론

A 알고리즘은 그래프 탐색 문제, 특히 최단 경로 탐색 문제에 강력한 해결책을 제시합니다. 휴리스틱 함수를 사용하여 탐색의 효율성을 높이고, 다양한 분야에서 실용적으로 활용될 수 있습니다. 알고리즘의 원리를 이해하고, 문제에 맞는 적절한 휴리스틱 함수를 설계하는 것이 A 알고리즘을 성공적으로 활용하기 위한 핵심입니다. 지속적인 학습과 문제 해결 경험을 통해 A* 알고리즘에 대한 이해도를 높일 수 있습니다.