핵심 요약
- 지도 애플리케이션은 수천만 개의 경로를 실시간으로 계산하기 위해 기본 알고리즘인 다익스트라(Dijkstra)의 연산 효율을 극대화하는 방식을 사용합니다.
- 다익스트라 알고리즘은 탐색 범위가 지나치게 넓다는 한계가 있어, 이를 극복하기 위해 경로의 계층을 나누고 사전에 지름길(Shortcuts)을 계산하는 ‘맞춤형 축소 계층(Customizable Contraction Hierarchies)’ 기법을 도입합니다.
- 이 방식은 경로 탐색 시 중요도가 높은 도로 위주로 우선 탐색하게 함으로써, 단순 다익스트라 대비 탐색 속도를 약 35,000배 이상 단축하여 실시간 서비스 수준을 구현합니다.
주요 내용
1. 최단 경로 탐색의 기초: 다익스트라(Dijkstra)
에츠허르 다익스트라가 1956년 고안한 이 알고리즘은 가중치가 있는 그래프에서 시작점에서 모든 노드까지의 최단 거리를 보장합니다. 하지만 모든 방향을 균등하게 탐색하며 확장하기 때문에, 북미 도로망처럼 6,400만 개가 넘는 노드가 존재하는 대규모 시스템에서는 연산 시간이 지나치게 길어지는 문제(평균 7초 소요)가 발생합니다.
2. 효율 개선을 위한 시도
- A* (A-star) 알고리즘: 목적지까지의 직선거리를 휴리스틱(Heuristic)으로 활용하여, 탐색 방향을 목적지 쪽으로 편향시켜 탐색 범위를 줄입니다. 하지만 최단 이동 시간 최적화 상황에서는 성능이 떨어지는 한계가 있습니다.
- 양방향 탐색: 시작점과 목적지 양쪽에서 동시에 탐색을 시작하여 중간 지점에서 만나게 함으로써 탐색 공간을 절반 이상으로 줄입니다.
3. 현대적 해결책: 맞춤형 축소 계층(CCH)
실제 도로망에는 고속도로와 같은 상위 도로와 작은 골목길 같은 하위 도로의 ‘계층(Hierarchy)’이 존재합니다.
- 전처리 단계: 그래프의 중요도를 기준으로 노드 순위를 매기고, 하위 경로를 대체할 ‘지름길(Shortcut)’을 미리 계산해 둡니다.
- 핵심 원리: 중요도가 높은 노드(예: 큰 강을 건너는 다리)를 우선 탐색하고, 미리 계산된 지름길을 활용하여 불필요한 저차원 도로 탐색을 건너뜁니다.
- 성과: 이 기법을 사용하면 탐색 대상 노드를 1,450개 수준으로 대폭 줄여 1밀리초(ms) 미만의 응답 속도를 달성할 수 있습니다.
핵심 데이터 / 비교표
| 지표 | 단순 다익스트라 | 맞춤형 축소 계층(CCH) |
|---|---|---|
| 북미 네트워크 경로 계산 시간 | 약 7초 | 약 200 마이크로초(μs) |
| 평균 탐색 노드 수 | 약 6,400만 개 | 약 1,450개 |
| 검색 효율 개선율 | - | 약 44,000배 (탐색 공간 기준) |
타임스탬프별 핵심 포인트
| 시간 | 핵심 내용 | | :— | :— | | 00:00 | 최단 경로 문제와 방대한 데이터 규모 | | 03:00 | 다익스트라 알고리즘의 원리 | | 07:15 | A* 알고리즘과 휴리스틱의 개념 | | 13:40 | 도로 네트워크의 계층 구조와 필요성 | | 15:50 | 중첩 해부(Nested Dissection)와 노드 중요도 | | 19:40 | 지름길(Shortcuts)을 통한 최적화 | | 21:00 | 맞춤형 축소 계층(CCH)의 성능 및 결론 |
결론 및 시사점
현대적인 경로 탐색 서비스는 70년 전 고안된 단순하고 우아한 알고리즘인 ‘다익스트라’를 근간으로 하되, 데이터를 사전에 정제하고 계층화하는 전략을 통해 실시간성을 확보하고 있습니다. 이는 문제 해결에 있어 알고리즘의 본질적 단순함을 유지하면서도, 시스템의 복잡도를 제어하는 구조적 접근이 얼마나 중요한지를 시사합니다.
추가 학습 키워드
- 그래프 이론 (Graph Theory)
- 휴리스틱 검색 (Heuristic Search)
- 중첩 해부 (Nested Dissection)
- 알고리즘 복잡도 (Algorithm Complexity)
- 도로 네트워크 계층화 (Road Network Hierarchy)
기본 정보
| 항목 | 내용 | |—|—| | 채널 | Veritasium | | 카테고리 | 과학기술 | | 게시일 | 2026-05-30 | | 영상 길이 | 29:54 | | 처리 엔진 | gemini-3.1-flash-lite+transcript | | 원본 영상 | YouTube에서 보기 |