A* 경로탐색 시각화
휴리스틱 기반 최단 경로 탐색 A*(A-Star) 알고리즘을 시각적으로 학습합니다
탐색★★☆
속도
1 / 1탐색 노드: 0대기열 크기: 0
그리드 크기15 x 20
시작점 목표점 벽 탐색 완료 탐색 대기 최단 경로
A*가 어떻게 최소 비용 노드를 선택하는지 관찰하세요.
탐색 중: ({x}, {y})
A* 알고리즘이란?
A*(A-Star)는 그래프에서 최단 경로를 효율적으로 찾는 알고리즘입니다. 다익스트라 알고리즘에 휴리스틱(목표까지의 예상 거리)을 추가하여 탐색 방향을 안내합니다. 게임 AI, 로봇 내비게이션, GPS 경로 탐색 등에 널리 사용됩니다.
사용 방법
- 1그리드를 클릭/드래그하여 벽을 그리거나 지우세요
- 2시작점(녹색)과 목표점(빨간색)을 설정하세요
- 3휴리스틱 종류(맨해튼/유클리드/체비셰프)를 선택하세요
- 4대각선 이동 옵션을 켜면 8방향 탐색이 가능합니다
- 5비용 표시를 켜면 각 셀의 f/g/h 값을 볼 수 있습니다
- 6A* vs BFS 비교 모드로 효율성 차이를 확인하세요
동작 원리
- 1시작 노드를 오픈 리스트(우선순위 큐)에 추가하고 f(n) = g(n) + h(n)을 계산합니다. g(n)은 시작에서 현재까지의 실제 비용, h(n)은 현재에서 목표까지의 예상 비용(휴리스틱)입니다.
- 2f값이 가장 작은 노드를 꺼내 현재 노드로 설정합니다. 현재 노드가 목표이면 경로를 역추적하고 종료합니다.
- 3인접 노드들의 g값을 갱신하고, 더 좋은 경로가 발견되면 부모 노드를 업데이트합니다.
- 4오픈 리스트가 빌 때까지 반복하며, 비어있으면 경로가 없음을 의미합니다.
실무 활용
- •게임 NPC의 경로 탐색(Starcraft, Age of Empires 등 RTS 게임)에서 실시간으로 경로를 계산합니다.
- •로봇 청소기/드론의 실시간 경로 계획과 자동차 네비게이션의 도로 네트워크 최단 경로에 사용됩니다.
- •물류 배송 경로 최적화와 퍼즐 게임 풀이(15-puzzle, 루빅스 큐브)에 활용됩니다.
- •H3/S2 지리 인덱싱을 사용하는 지도 서비스에서 실제 도로망 경로 탐색에 적용됩니다.
비슷한 알고리즘
- •다익스트라 vs A* — 다익스트라는 h(n)=0인 A*의 특수 케이스입니다. 휴리스틱 없이 모든 방향을 균등 탐색하여 목적지 없이 전체 최단 거리를 구할 때 유리합니다.
- •BFS — 비가중 그래프 전용 최단 경로 알고리즘입니다. 가중치가 없으면 A*보다 단순하고 빠릅니다.
- •JPS(Jump Point Search) — 그리드 맵 전용 A* 최적화로 대칭 경로를 건너뛰어 수십 배 빠릅니다. D* Lite는 동적 환경에서 경로를 점진적으로 수정하는 A* 변형입니다.
학습 팁
- •A*는 적합한 휴리스틱을 사용하면 최단 경로를 보장합니다
- •맨해튼 거리는 4방향 이동, 체비셰프 거리는 8방향 이동에 적합합니다
- •BFS와 비교하면 A*가 훨씬 적은 노드를 탐색하는 것을 확인할 수 있습니다
- •h=0이면 A*는 다익스트라 알고리즘과 동일하게 동작합니다
- •f값이 낮은 셀(밝은 색)이 우선 탐색되는 것을 관찰하세요
자주 묻는 질문
Q. A*가 항상 BFS보다 빠른가요?
A. 대부분의 경우 A*가 더 적은 노드를 탐색합니다. 하지만 휴리스틱이 부정확하거나 경로가 매우 짧으면 차이가 적을 수 있습니다.
Q. 어떤 휴리스틱을 선택해야 하나요?
A. 4방향 이동이면 맨해튼, 8방향이면 체비셰프가 최적입니다. 유클리드는 자유 이동에 적합하지만 그리드에서는 약간 비효율적일 수 있습니다.
Q. 시간 복잡도는 어떻게 되나요?
A. 최악의 경우 O(b^d)이지만 (b=분기 계수, d=깊이), 좋은 휴리스틱을 사용하면 실제로는 BFS보다 훨씬 빠릅니다.