구글 지도의 비밀: 드래그할 때마다 최단 경로를 다시 계산하는 A* 최적화

Differential Heuristics

2007년 구글 지도는 경로의 시작점과 끝점을 드래그하면 최단 경로를 실시간으로 다시 계산하는 기능을 선보였다. 이는 수백만 개의 도로를 가진 전 세계 지도에서 빠른 A* 경로 탐색을 가능하게 한 기술이었다. 저자는 2005년부터 이 기술에 매료되어 수년간 연구해 왔으며, 2014년 A* 안내서를 작성한 후 2024년까지 여러 차례 튜토리얼을 시도했지만 만족스러운 설명을 찾지 못했다. 결국 학습과 실험 모드로 전환하여 '차등 휴리스틱(Differential Heuristics)'을 더 깊이 이해하게 되었고, 화살표 시각화와 개선 영역 표시 등 새로운 설명 방식을 개발했다. 이 글은 그가 10년 만에 공개한 차등 휴리스틱에 대한 새로운 가이드를 소개한다.