이 실험 소개
지도 경로 탐색, 로봇, 비디오 게임은 모두 같은 문제를 해결합니다. 시작점에서 목표점까지 가장 비용이 적게 드는 길을 찾는 것이죠. 이 격자에서는 도로로 한 칸 이동하는 비용은 1, 진흙으로 들어가는 비용은 5이며, 벽은 통과할 수 없습니다. S에서 퍼져 나가는 세 가지 고전 알고리즘을 살펴보세요. 너비 우선 탐색은 이동 횟수를 세고 진흙은 고려하지 않습니다. 다익스트라 알고리즘은 다음에 비용이 가장 낮은 칸을 항상 탐색하고, A*는 남은 거리의 추정치를 더해 목표를 향해 곧장 나아갈 수 있게 합니다. 직접 지도를 색칠하고 각 알고리즘이 얼마나 많은 작업을 하는지 비교해 보세요.
학습 목표
- 지도를 이웃 칸들이 연결되고 각 이동에 비용이 있는 그래프로 표현하기
- 너비 우선 탐색이 이동 횟수가 같은 칸들을 고리 모양으로 탐색하는 방식을 설명하기
- 단계마다 비용이 다를 때 다익스트라 알고리즘이 가장 저렴한 경로를 찾는 이유를 설명하세요
- A*의 휴리스틱이 최적의 경로를 놓치지 않으면서 탐색하는 셀 수를 줄이는 방식을 설명하세요
- 각 알고리즘이 찾는 경로의 비용과 수행하는 작업량을 비교하세요
사용 방법
- 1BFS를 선택하고 검색을 누르세요. 찾은 경로가 진흙을 지나가나요? 표에서 비용을 확인하세요.
- 2다익스트라를 선택하고 다시 검색하세요. BFS의 경로와 비용을 비교하세요.
- 3A*를 선택하세요. 경로 비용이 다익스트라와 같나요? 탐색한 셀 수가 얼마나 줄었나요?
- 4검색 중 파란색 프런티어를 살펴보세요. 다익스트라와 A*에서 그 모양은 어떻게 다른가요?
- 5진흙 주변의 길을 막도록 벽을 칠하세요. 어떤 알고리즘이 경로를 바꾸며, 그 이유는 무엇인가요?
- 6지도 지우기를 누르고 S와 G를 서로 멀리 떨어뜨리세요. 장애물이 없을 때 각 알고리즘은 셀을 몇 개 탐색하나요?
모델
가정
- 이동은 위, 아래, 왼쪽, 오른쪽으로만 가능합니다. 칸에 들어가는 비용은 도로에서는 1, 진흙에서는 5이며, 벽에는 들어갈 수 없습니다.
- BFS는 탐색 중 모든 이동의 비용을 1로 취급하므로 이동 횟수가 가장 적은 경로를 찾습니다. 표에 표시된 해당 경로의 비용은 진흙 구간을 포함한 실제 비용입니다.
- 두 칸의 우선순위가 같으면 먼저 추가된 칸을 먼저 탐색하므로, 같은 지도에서는 실행할 때마다 정확히 같은 순서로 탐색합니다.
- 목표가 프런티어에서 꺼내지는 즉시 탐색을 멈춥니다. 그때 목표까지의 최저 비용을 알 수 있기 때문입니다.
수업에서 해 보기
- Q1BFS는 이동 횟수가 더 적은데도 왜 다익스트라보다 비용이 더 큰 경로를 찾을 수 있을까요?
- Q2모든 칸이 도로라면 BFS와 다익스트라는 비용이 같은 경로를 찾을까요? 왜 그럴까요?
- Q3추정값 h가 맨해튼 거리의 10배라면 A*에는 어떤 일이 일어날까요?
- Q4목표가 탁 트인 곳에 있으면 A*는 왜 더 적은 칸을 탐색하지만, 미로에서는 다익스트라와 거의 같은 수의 칸을 탐색할까요?
- Q5내비게이션은 수백만 개의 도로 교차로가 있는 나라를 가로지르는 빠른 경로를 1초도 안 되어 찾습니다. 이 실험에서 배운 어떤 개념들이 이를 가능하게 할까요?
자주 묻는 질문
가장 좋은 알고리즘은 무엇인가요?
문제에 따라 다릅니다. 모든 이동 비용이 같다면 BFS는 간단하고 정확합니다. 이동 비용이 서로 다르면 다익스트라 알고리즘을 사용합니다. 목표까지의 거리를 잘 추정할 수 있다면 A*는 다익스트라 알고리즘과 같은 답을 찾으면서도 더 적은 칸을 탐색합니다.
프런티어란 무엇인가요?
프런티어는 도달했지만 아직 탐색하지 않은 칸들의 집합입니다. 각 알고리즘은 한 번에 프런티어에서 칸 하나를 꺼냅니다. 알고리즘 간의 차이는 다음에 어떤 칸을 꺼낼지 정하는 규칙뿐입니다.
이 알고리즘들은 음수 비용을 처리할 수 있나요?
다익스트라 알고리즘과 A*는 이동 비용이 음수인 경우가 없다고 가정합니다. 음수 비용이 있으면 이미 확정된 칸에 나중에 더 저렴한 경로가 발견될 수 있으므로, 벨만-포드 알고리즘과 같은 다른 알고리즘이 필요합니다.