네비게이션, 네덜란드 수학자 딕스트라의 20분으로 탄생 (6/8 월)

네비게이션의 수학 (6/8 월)

안녕하세요! 아주대학교 총장 박형줍니다. 차량 네비는 GPS 수신기를 이용해서 목적지까지 가는 방법을 가르쳐주는 장치인데요. 최초의 차량 네비는 1995년에 GM이 처음 출시했어요. 2천 달러의 유상 옵션이었는데도 엉뚱한 길을 알려주곤 해서 불평이 많았다고 하죠. 인공위성을 통해 내 위치를 파악하는 GPS는 1970년대에 이미 나왔는데, 이걸 이용해서 목표 지점까지 이동하는 경로를 찾는 차량 네비는 왜 20여 년이 지나서야 개발됐을까요?

지도 상의 한 지점에서 다른 지점으로 가는 경로가 한 둘이 아니다보니, 가능한 경로들을 모두 비교해서 그 중에 가장 빠른 길을 찾아야 하는데, 10개의 도시가 이리저리 연결되어 있는 지도만 해도 한 도시에서 다른 도시로 가는 경로가 아마무시하게 많습니다. 도시 숫자가 늘면 슈퍼컴퓨터로도 다 비교 못 할 정도로 가능한 경로가 무궁무진해요. 계산이 몹시 어려운 이런 문제를 NP 문제라고 부릅니다.

이런 문제를 풀려면, 최선이 아닌 차선의 경로일지라도 계산 시간을 획기적으로 줄이는 근사해를 찾을 수밖에 없어요. 이걸 고민하던 사람들은, 네덜란드의 수학자인 딕스트라(Edsger Dijkstra)가 1959년에 출간한 논문에 이미 답이 있었다는 걸 발견했어요. 사람들은 딕스트라의 업적을 까맣게 잊고 있다가, GPS가 발명되고 난 후에 네비를 개발 과정에서 재발견한거에요. 요즘의 구글 지도는, 조금 돌아가는 길이라도 신속하게 찾는 걸 더 중시하는 방식으로 딕스트라 알고리즘을 변형해서 사용합니다.

딕스트라는 젊은 시절에 잠시 생각해서 얻은 이 결과가 자신의 가장 유명한 업적이 된 것을 신기해했다고 합니다. 1956년에 20대의 젊은이였던 그는 카페에서 커피를 마시며 최단 경로 문제를 생각했는데, 마침 펜과 종이가 없었어요. 복잡한 계산을 할 수 없으니 간단한 방법만 생각할 수밖에 없었는데, 결국 20분쯤 걸려서 답을 구했죠. 아무리 많은 GPS 위성을 쏘고 내 위치를 정확하게 알아도, 26세 젊은이의 그 20분이 없었더라면, 오늘 대전에서 서울까지 어떤 경로로 가야 가장 빠를지 몰랐을 거에요. 이제는 구글 지도부터 스마트폰의 네비 앱까지 딕스트라 알고리즘 또는 그 변형을 사용합니다.

‘가장 단순한 방법을 생각할 수밖에 없는 상황이 되면 그렇게 되더라’라고 딕스트라는 말했습니다. 앞으로 정말 중요한 문제를 생각할 때는 종이와 연필을 치워보시면 어떨까요.