구글 트립에 들어간 280년 전 알고리즘

구글 트립(Google Trips)은 구글이 지난 20일 발표한 것으로 여행 정보를 편리하게 관리할 수 있게 해주는 앱. 목적지까지 이동 방법과 도착, 이동 시간 또 관광지 위치와 근처에 있는 레스토랑 등 다양한 정보를 바탕으로 여행 계획표를 자동으로 만들 수 있다. 그런데 구글에 따르면 구글 트립에 이용한 알고리즘은 무려 280년 전의 것을 바탕으로 한 것이다. 앞서 설명했듯 구글 트립은 여행 현지에 가기 전에 하루 상세 일정을 짤 수 있는 앱. 여행 길잡이 역할을 해 최적의 여행 계획으로 알 수 있다. 그런데 여기에 쓰인 알고리즘은 280년 전에 나왔다는 것이다. 스위스 학자인 레온하르트 오일러(Leonhard Euler)는 당시 독일 도시인 쾨니히스베르크에 있는 다리 7개에 관한 수학적 논문을 1736년 집필했다. 한 신문이 다리 7개를 연이어 모두 통과하는 게 가능하냐는 내용에 오일러가 불가능하다고 답한 것. 그는 육지와 다리 레이아웃을 표현하는 방법을 고안한 뒤 ‘Geometriam Situs’라고 명명했다. 오일러가 발안한 건 현대 수학 이론 중 하나인 그래프 이론이다. 그래프 이론은 노드, 접점 6개와 접점을 연결하는 변의인 엣지로 이뤄진 그래프에 관한 이론으로 오일러는 육지를 노드, 다리를 가장자리로 표현했다. 오일러는 쾨니히스베르크에는 맞지 않지만 노드에 접하는 모서리 수가 각 노드와 같을 경우에만 한번에 연결이 가능하다는 걸 알게 된다. 구글은 이를 바탕으로 어떻게 하면 많은 관광 명소를 한 번에 돌 수 있을지에 대한 의문을 해소하기 위해 여행 일정 문제로 명명하고 조사를 실시했다. 이 문제를 해결하려면 관광지 픽업과 픽업 관광지를 여행 일정에 포함하는 2가지 목적을 달성할 수 있다. 구글은 두 번째 중에서 이동 시간 단축과 관광지가 닫혀 있다면 방문하지 않는다거나 미술관 같은 명소를 연속 방문하는 식으로 과제에 따라 효율이 좋은 길 찾기 알고리즘을 구축하는 데 애를 먹었다고 한다. 효율이 좋은 경로 검색을 위해 구글은 크리스토피드 알고리즘(Christofides algorithm)을 이용했다. 크리스토피드 알고리즘을 이용해 여러 거리를 이동하는 이동 경로 중에서도 가장 짧은 걸 검색 결과로 제시할 수 있게 됐다는 것이다. 효율적인 경로 검색 알고리즘을 구축한 뒤 관광 명소를 방문해 얻을 수 있는 장점, 관광 명소 입장료를 계산한다. 이미 방문한 관광 명소와의 차이 등을 이용해 도출하는 것. 런던 관광 루트를 구축하는 걸 예로 들면 웨스트민스터사원에서 빅벤까지 왕복 루트를 알고리즘으로 이용하면 웨스터민스터 사원에서 세인트제임스 파크, 빅벤, 버킹엄 궁전, 하이드 파크를 도는 루트를 제공한다. 구글 트립은 또 자신의 친구는 이런 장소를 추천한다거나 관광을 할 수 있는 시간이 아침 뿐이고 오후 일정에 포함된 관광지도 아침에 가고 싶다는 등 사용자의 개인적 요구에 응할 수 있는 알고리즘도 통합하고 있다. 관련 내용은 이곳( https://research.googleblog.com/2016/09/the-280-year-old-algorithm-inside.html )에서 확인할 수 있다.