내비게이션은 어떻게 가장 빠른 길을 찾는가

내비게이션이 가장 빠른 길을 찾는 일은 수학적으로는 그래프에서 최단 경로를 찾는 문제다. 교차로를 점으로, 도로를 점을 잇는 선으로 보고, 각 선에 걸리는 시간을 적어 두면 길 찾기는 출발점에서 도착점까지 시간 합이 가장 작은 선들의 연결을 찾는 계산이 된다. 이 계산의 기본 원리는 1950년대에 나왔고, 오늘날의 내비게이션은 그 위에 거대한 도로망을 빠르게 다루는 기술을 덧붙였다.

모든 길을 다 비교하면 안 되나

가능한 길을 하나도 빼놓지 않고 모두 따져 보면 가장 빠른 길을 확실히 찾을 수 있다. 문제는 그 수다. 교차로가 조금만 늘어도 가능한 길의 조합은 폭발적으로 불어난다. 서울 시내만 해도 교차로가 수만 개이고, 이들을 잇는 경로의 경우의 수는 상상하기 어려울 만큼 많다. 모든 길을 비교하는 방식으로는 아무리 빠른 컴퓨터로도 답을 낼 수 없다.

다익스트라 알고리즘은 어떻게 길을 넓혀 가나

1950년대 네덜란드의 컴퓨터 과학자 에츠허르 다익스트라는 훨씬 영리한 방법을 내놓았다. 출발점에서 가까운 곳부터 차례로 확정해 나가는 것이다.

처음에는 출발점까지의 시간이 0이고 나머지는 모두 모른다. 출발점과 직접 이어진 교차로들까지의 시간을 적는다. 그중 가장 가까운 교차로를 하나 골라 '확정'한다. 이 교차로까지는 더 빠른 길이 있을 수 없다. 다른 모든 후보가 이미 그보다 멀기 때문이다. 이제 확정한 교차로에서 다시 이어진 곳들의 시간을 갱신하고, 아직 확정하지 않은 것 가운데 가장 가까운 곳을 또 확정한다. 이 과정을 도착점이 확정될 때까지 반복한다.

마치 출발점에 돌을 던져 물결이 퍼져 나가듯, 가까운 곳부터 차례로 답이 정해진다. 모든 길을 비교하지 않고도 정확한 최단 경로를 보장한다는 점이 이 방법의 힘이다.

왜 엉뚱한 방향까지 탐색하지 않나

다익스트라의 방법은 정확하지만 방향을 가리지 않는다. 부산으로 가는 길을 찾으면서 북쪽으로도 똑같이 물결을 넓힌다. 그래서 목적지 쪽을 우선해서 살피는 개선이 나왔다. 대표적인 것이 A* 알고리즘이다. 각 교차로에서 목적지까지 남은 거리를 대략 짐작해, 지금까지 온 시간과 앞으로 남은 예상 시간을 더한 값이 작은 곳부터 살핀다. 남은 거리를 실제보다 크게 짐작하지만 않으면 여전히 정확한 답을 찾으면서도 살펴야 할 교차로가 크게 줄어든다.

방법	살피는 방식	특징
모든 길 비교	가능한 경로를 전부 계산	정확하지만 현실적으로 불가능
다익스트라	가까운 곳부터 차례로 확정	정확, 방향 구분 없음
A*	목적지까지 남은 거리를 함께 고려	정확, 탐색 범위가 줄어듦
미리 계산해 두기	중요한 도로를 미리 정리	거대한 도로망에서 매우 빠름

전국 단위 도로망에서는 이것으로도 부족하다. 그래서 실제 서비스는 도로를 미리 분석해 둔다. 골목길보다 고속도로와 간선도로를 우선하는 계층을 만들어 두고, 먼 거리를 갈 때는 큰 도로 위주로 계산한다. 시간이 오래 걸리는 준비 작업을 미리 해 두고, 실제 질문에는 그 결과를 이용해 빠르게 답하는 방식이다.

막히는 길은 어떻게 반영하나

가장 빠른 길은 도로의 길이가 아니라 걸리는 시간으로 정해진다. 내비게이션은 도로마다 걸리는 시간을 교통 정보로 계속 갱신한다. 같은 출발점과 도착점이라도 출근 시간과 새벽의 답이 다른 이유다. 출발 시각에 따라 도로의 예상 소요 시간을 달리 적용하기도 한다.

남은 과제

모두가 같은 내비게이션의 같은 추천을 따르면 그 길이 곧 막힌다. 한 사람에게 가장 빠른 길을 알려 주는 것과 도시 전체의 흐름을 좋게 만드는 것은 다른 문제다. 여러 차량에 경로를 나눠 안내해 전체 정체를 줄이는 방법이 연구되지만, 각자에게 손해가 되는 길을 안내받는 운전자가 생긴다는 점에서 쉽지 않은 숙제로 남아 있다. 앞으로의 교통 상황을 정확히 예측하는 일도 여전히 어렵다.