경로탐색 비교 (A* vs Dijkstra)
A*와 다익스트라를 동일 맵에서 동시 실행하여 탐색 범위와 효율성을 시각적으로 비교하세요
탐색★☆☆
속도
1 / 1A* 탐색Dijkstra 탐색양쪽 탐색A* 경로Dijkstra 경로
배치 모드
A*(파랑)와 Dijkstra(주황)가 동시에 탐색하는 과정을 관찰하세요.
A* vs Dijkstra
A*는 휴리스틱으로 목표 방향을 우선 탐색하여 불필요한 탐색을 줄입니다. Dijkstra는 모든 방향을 균일하게 탐색합니다.
재생 버튼을 눌러 비교를 시작하세요.
A* vs Dijkstra
두 알고리즘 모두 최단 경로를 찾지만, A*는 목표까지의 추정 거리(휴리스틱)를 활용하여 더 적은 노드를 탐색합니다. Dijkstra는 균일하게 확장합니다.
사용 방법
- 1벽을 그려 장애물을 만들거나 미로를 생성하세요
- 2시작점(S)과 도착점(E)을 배치하세요
- 3재생 버튼으로 두 알고리즘의 동시 탐색을 관찰하세요
- 4완료 후 방문 노드 수와 경로 길이를 비교하세요
학습 팁
- •열린 공간에서는 A*가 훨씬 적은 노드를 탐색합니다
- •미로에서는 두 알고리즘의 차이가 줄어듭니다
- •파란색(A*)과 주황색(Dijkstra) 탐색 영역의 모양을 비교하세요
- •보라색은 두 알고리즘 모두 탐색한 영역입니다
자주 묻는 질문
Q. A*가 항상 더 빠른가요?
A. 대부분 빠르지만, 모든 경로 비용이 비슷한 경우 Dijkstra와 동일합니다. 휴리스틱이 정확할수록 유리합니다.
Q. 경로 길이는 같은가요?
A. 네, 두 알고리즘 모두 최단 경로를 보장합니다. 차이는 탐색하는 노드 수입니다.
Q. 휴리스틱이란?
A. 현재 위치에서 목표까지의 추정 비용입니다. Manhattan 거리(|dx|+|dy|)를 사용합니다.