[고급 알고리즘] A* 알고리즘 (A-star Algorithm)

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

개요

A* 알고리즘은 그래프 내의 두 노드 사이의 최단 경로를 찾는 데 사용되는 탐색 알고리즘입니다. 이 알고리즘은 각 노드의 예상 비용을 기반으로 최적의 경로를 빠르게 찾을 수 있습니다. A*는 다양한 응용 분야에서 사용되며, 특히 경로 찾기와 그래프 탐색 문제에서 널리 사용됩니다.

특징

1. 휴리스틱 평가: A* 알고리즘은 휴리스틱 함수를 사용하여 각 노드의 예상 비용을 추정합니다. 이 함수는 현재 노드에서 목표 노드까지의 예상 최소 비용을 반환합니다.
2. 최적성: 올바른 휴리스틱 함수를 사용하면 A* 알고리즘은 항상 최적의 경로를 찾을 수 있습니다.
3. 효율성: A*는 경로의 예상 비용을 기반으로 노드를 확장하므로, 불필요한 경로를 탐색하는 것을 피하면서 효율적으로 작동합니다.
4. 활용 분야: A* 알고리즘은 게임 개발, 로봇 경로 계획, 지도 서비스 등 다양한 분야에서 활용됩니다. 특히, 실시간 시스템에서는 빠른 응답 시간이 필요하기 때문에 A*와 같은 효율적인 알고리즘이 필요합니다.

예시

A* 알고리즘이 어떻게 작동하는지 이해하기 위해 간단한 예를 들어보겠습니다. 두 도시 사이의 최단 경로를 찾는 문제를 생각해보세요. 각 도시는 그래프의 노드로 표현되며, 도로는 간선으로 표현됩니다. A* 알고리즘은 시작 도시에서 목표 도시까지의 경로를 찾기 위해 휴리스틱 함수를 사용하여 각 도시의 예상 비용을 계산합니다. 이 비용은 현재 도시에서 목표 도시까지의 직선 거리를 기반으로 합니다. A*는 이 예상 비용을 사용하여 최적의 경로를 빠르게 찾을 수 있습니다.

import heapq

def a_star(graph, start, goal):
    open_list = []
    heapq.heappush(open_list, (0, start))
    came_from = {}
    g_score = {node: float('inf') for node in graph}
    g_score[start] = 0
    f_score = {node: float('inf') for node in graph}
    f_score[start] = heuristic(start, goal)

    while open_list:
        _, current = heapq.heappop(open_list)

        if current == goal:
            return reconstruct_path(came_from, current)

        for neighbor in graph[current]:
            tentative_g_score = g_score[current] + 1

            if 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)
                heapq.heappush(open_list, (f_score[neighbor], neighbor))

    return None

def heuristic(node, goal):
    # This is an example heuristic function, you can replace it with your own
    return abs(node[0] - goal[0]) + abs(node[1] - goal[1])

def reconstruct_path(came_from, current):
    path = [current]
    while current in came_from:
        current = came_from[current]
        path.append(current)
    path.reverse()
    return path

이 코드는 A* 알고리즘을 구현한 예시입니다. a_star 함수는 주어진 그래프, 시작 노드, 목표 노드를 사용하여 최단 경로를 찾습니다. heuristic 함수는 두 노드 사이의 휴리스틱 값을 계산하며, reconstruct_path 함수는 찾은 경로를 반환합니다.

 

시간 복잡도

A* 알고리즘의 시간 복잡도는 사용하는 휴리스틱 함수와 그래프의 구조에 따라 다릅니다. 일반적으로 A*의 시간 복잡도는 O(b^d)로 추정되며, 여기서 b는 각 노드의 평균 분기 계수이고 d는 목표 노드까지의 깊이입니다.