플로리다 경로 탐색에서 세 알고리즘은 같은 길을 찾는다

플로리다 도로망 경로를 그린 애니메이션에서 세 알고리즘의 답이 초 단위까지 같습니다. 탈라해시에서 코럴게이블스까지 이동 시간을 기준으로 계산한 결과입니다. 비교되는 것은 디익스트라(Dijkstra), A*와 설정형 수축 계층(Customizable Contraction Hierarchy)입니다. 저는 같은 답보다 각 방식이 답을 찾기 전 살펴야 하는 도로 영역을 함께 보여 준 점이 오래 남습니다. 맞는 길을 찾는 일과 그 길을 찾는 과정은 다른 문제이기 때문입니다.

샌프란시스코의 Flatten SF는 거리와 누적 오르막을 조절해 걷기·자전거 경로를 찾는 체험 페이지입니다. 플로리다의 애니메이션은 이동 시간 기준을 고정하고 계산 방식별 탐색 범위를 보여 줍니다. 반면 Flatten SF에서는 사용자가 거리와 오르막이라는 기준을 바꿉니다. 두 경험은 길찾기 결과를 만드는 기준과 과정이 사용자 선택과 맞닿아 있음을 보여 줍니다.

길찾기 결과만 볼 때는 목적지와 도착 시간만 남습니다. 이 애니메이션은 교차로 107만 개와 도로 구간 270만 개로 이뤄진 실제 도로망을 보여 줍니다. 색칠된 사각형은 각 방식이 답을 알기 전에 탐색해야 하는 주 내 영역을 나타냅니다. 답이 같더라도 탐색은 달라질 수 있다는 점을 한눈에 보여 주는 것이 반갑습니다.

경로는 탈라해시에서 코럴게이블스까지이며 이동 시간 기준입니다. 디익스트라와 A*는 정확한 답을 내고 사전 준비가 필요 없지만, 두 지점이 멀수록 더 많은 도로망을 읽습니다. 세 방식의 결과가 일치했다는 사실만으로 계산 속도까지 같거나 다른 경로에서도 결과가 같다고 말할 수는 없습니다.

애니메이션을 재생하며 세 알고리즘의 최종 경로와 색칠된 사각형의 범위를 비교하십시오. 색칠된 영역을 살펴보면 경로 결과와 탐색 범위가 별개로 표시된다는 점을 직접 확인할 수 있습니다.

길찾기 앱에서 비슷한 예상 시간의 경로가 여럿 나왔을 때, 마지막으로 무엇을 보고 하나를 고르셨습니까?