구글 지도의 비밀: 드래그할 때마다 최단 경로를 다시 계산하는 A* 최적화
Differential Heuristics
2007년 구글 지도는 경로의 시작점과 끝점을 드래그하면 최단 경로를 실시간으로 다시 계산하는 기능을 선보였다. 이는 수백만 개의 도로를 가진 전 세계 지도에서 빠른 A* 경로 탐색을 가능하게 한 기술이었다. 저자는 2005년부터 이 기술에 매료되어 수년간 연구해 왔으며, 2014년 A* 안내서를 작성한 후 2024년까지 여러 차례 튜토리얼을 시도했지만 만족스러운 설명을 찾지 못했다. 결국 학습과 실험 모드로 전환하여 '차등 휴리스틱(Differential Heuristics)'을 더 깊이 이해하게 되었고, 화살표 시각화와 개선 영역 표시 등 새로운 설명 방식을 개발했다. 이 글은 그가 10년 만에 공개한 차등 휴리스틱에 대한 새로운 가이드를 소개한다.
거의 모든 논문에 대한 나의 반응은 '지도가 매우 크지 않다면 이 복잡성은 가치가 없다'는 것이었다.
- plomme
Red Blob의 글은 언제나 그렇듯이 아주 훌륭한 분석입니다. 이 글 덕분에 구글 지도 경로 탐색에 대한 제 고수준 가정이 완전히 뒤집혔습니다. 알고리즘 수업을 떠올려 보면, 구글 지도가 이렇게 빠른 이유가 최단 경로 찾기의 '최적 부분 구조' 때문이라고 생각했습니다. 즉, A에서 C로 가는 최단 경로가 B를 경유한다면, 그 경로는 A에서 B, B에서 C로 가는 최단 경로이기도 하다는 것입니다. 그리고 주어진 경로의 대부분은 미리 계산된 '중간 지점' 경로들을 통해 라우팅할 수 있다고 생각했습니다. 그런데 이 글을 읽고 나니, 랜드마크가 경로의 중간이 아니라 목적지 뒤쪽에 있다는 점에서 제 생각이 완전히 뒤집혔습니다. 정말 유용한 도구네요.
- simonw
5일 전에 여기서 논의되었습니다: https://news.ycombinator.com/item?id=49079995
(솔직히 말하면, 이건 너무 멋진 작업이라 두 번째 대화를 할 가치가 충분합니다. 그 글은 댓글이 40개밖에 안 됐거든요.)
- inigyou
좋은 글과 데모네요. 색상에 대해 약간 혼란스러웠습니다. 적어도 한 번은 본문에서 파란색 타일이 랜드마크 때문에 확인할 필요가 없는 타일이라고 말하는데, 실제로는 초록색이고, 파란색은 어차피 확인되지 않은 타일입니다. 저는 색맹이 아닙니다.
지도 중 상당수가 몇 개의 지점에서 연결된 방들로 구성되어 있네요. 먼저 방들의 그래프를 통해 경로 탐색을 수행한 다음 각 방을 개별적으로 탐색하는 것을 고려해 보셨나요? 한 방에서 다른 포털로 가는 모든 경로를 미리 계산할 수도 있지만, 그럴 필요는 없을 것입니다. 다만 각 경로의 비용은 미리 계산해야 할 것입니다. 이는 각 방에 랜드마크를 두는 것과 비슷한 경로 탐색 비용일 것입니다.