[WEEK03] A* 알고리즘

 

 

A* 알고리즘이란?

A* 알고리즘A-star Algorithm은 최단 경로 탐색 알고리즘 중 하나로, 다익스트라 알고리즘과 휴리스틱 탐색을 결합한 방식이다. 네비게이션 시스템, 게임 AI, 로봇 경로 탐색 등 다양한 분야에서 활용된다.

• 휴리스틱Heuristic: 특정 문제에 대한 근사적인 해결책을 찾기 위해 사용되는 경험적이고 규칙적인 방법이나 규칙. 불충분한 시간이나 정보로 인하여 합리적인 판단을 할 수 없거나, 체계적이면서 합리적인 판단이 굳이 필요하지 않은 상황에서 사람들이 빠르게 사용할 수 있게 보다 용이하게 구성된 간편 추론의 방법.
  [출처] 휴리스틱 알고리즘

A* 알고리즘의 원리

A* 알고리즘은 탐색할 노드를 선택할 때 다음의 비용 함수 $ f(n) $을 사용한다:

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

• $ g(n) $: 시작 노드에서 현재 노드까지의 실제 비용
• $ h(n) $: 현재 노드에서 목표 노드까지의 휴리스틱(추정) 비용
• $ f(n) $: 총 예상 비용 (작을수록 우선 탐색)

이러한 방식으로 A* 알고리즘은 최단 경로를 효율적으로 찾을 수 있다.

다익스트라 알고리즘과의 차이점

A* 알고리즘과 다익스트라 알고리즘은 둘 다 그래프에서 최단 경로를 찾는 방법이지만 몇 가지 차이점이 있다.

비교 항목	다익스트라 알고리즘	A* 알고리즘
탐색 방식	모든 가능한 경로를 탐색하여 최단 경로 보장	휴리스틱을 활용하여 유망한 경로를 우선 탐색
휴리스틱 사용	X	O （$ h(n) $ 사용）
탐색 속도	느림 （모든 노드를 탐색）	빠름 （최적 경로 방향으로 진행）
최적 해 보장	항상 최적 경로 보장	적절한 휴리스틱 사용 시 최적 경로 보장

 

즉, 다익스트라 알고리즘은 모든 경로를 탐색하여 항상 최단 경로를 찾지만, A* 알고리즘은 휴리스틱을 활용해 탐색 범위를 줄여 더 빠르게 최단 경로를 찾을 수 있다.

휴리스틱 함수의 선택

휴리스틱 함수 $ h(n) $의 선택이 알고리즘 성능에 큰 영향을 미친다. 대표적인 휴리스틱 함수로는 다음이 있다:

• 맨해튼 거리: $|x_1 - x_2| + |y_1 - y_2|$ → 격자 기반 경로 탐색에서 자주 사용
• 유클리드 거리: $ \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2} $
• 체비쇼프 거리: 최대 좌표 차이를 사용한 거리 계산

💻 코드 구현

import heapq

def a_star(graph, start, goal, heuristic):
    open_list = []
    heapq.heappush(open_list, (0, start))
    came_from = {}
    g_score = {node: float('inf') for node in graph}
    g_score[start] = 0
    
    while open_list:
        _, current = heapq.heappop(open_list)
        
        if current == goal:
            path = []
            while current in came_from:
                path.append(current)
                current = came_from[current]
            return path[::-1]
        
        for neighbor, cost in graph[current].items():
            tentative_g_score = g_score[current] + cost
            if tentative_g_score < g_score[neighbor]:
                came_from[neighbor] = current
                g_score[neighbor] = tentative_g_score
                f_score = tentative_g_score + heuristic(neighbor, goal)
                heapq.heappush(open_list, (f_score, neighbor))
    
    return None

A* 알고리즘의 장단점

✅ 장점

• 다익스트라 알고리즘보다 빠르게 최적의 경로를 찾을 수 있음
• 탐색 속도가 빠르고, 다양한 휴리스틱 함수를 적용할 수 있음

❌ 단점

• 휴리스틱 함수가 적절하지 않으면 성능이 저하될 수 있음
• 메모리 사용량이 많아질 수 있음

정리

A* 알고리즘은 경로 탐색 문제에서 매우 강력한 도구이며, 휴리스틱 함수를 잘 선택하면 효율적인 탐색이 가능하다.

---

읽어보기

• A* 알고리즘에 대해 알아보자
• 휴리스틱 탐색 기법
• A* 알고리즘 grid map 개념 및 구현
• A* 알고리즘이 도대체 뭔데??