A* 알고리즘

A* 알고리즘

휴리스틱 함수를 사용하여 시작 노드에서 목표 노드까지의 최단 경로를 효율적으로 탐색하는 그래프 탐색 알고리즘으로, Dijkstra와 Greedy Best-First Search를 결합하여 f(n) = g(n) + h(n) 비용 함수로 경로 평가

목적: 효율적 최단 경로, 휴리스틱 활용, 게임 AI, 로봇 경로 계획

특징: 휴리스틱 기반, 최적성 보장(admissible h), 우선순위 큐, Dijkstra 일반화

비용 함수: f(n) = g(n) + h(n), g(n) = 시작부터 n까지 실제 비용, h(n) = n부터 목표까지 휴리스틱 추정 비용

휴리스틱 함수(h): Admissible(실제 비용 이하 추정 → 최적 보장), Consistent(단조성, h(n) ≤ c(n,n') + h(n'))

휴리스틱 예시: 맨해튼 거리(그리드), 유클리드 거리(평면), 체비셰프 거리(대각 이동)

동작: ① 시작 노드를 Open List에 추가 → ② f(n) 최소 노드 선택 → ③ 목표 도달 시 경로 반환 → ④ 인접 노드 평가 → ⑤ 반복

시간 복잡도: O(b^d), b = 분기 인수, d = 최적 경로 깊이, 휴리스틱 품질에 따라 개선

공간 복잡도: O(b^d) - Open/Closed List

장점: 최적 경로 보장(admissible h), Dijkstra보다 빠름, 휴리스틱 활용

단점: 메모리 사용 많음, 휴리스틱 설계 어려움, 동적 환경 제한

적용사례: 게임 AI(유닛 경로), GPS 내비게이션, 로봇 경로 계획, 퍼즐 해결(15-퍼즐)

비교: A*(휴리스틱/최적/빠름) vs Dijkstra(균등탐색/최적/느림) vs Greedy(휴리스틱만/비최적/빠름)

연관: Dijkstra, 휴리스틱, 게임 AI, 경로 탐색, Admissible