8만여 곳 가는 데 178일 소요 경찰청 ‘술집 위치정보’ 데이터 컴퓨터 여러 대를 병렬로 연결 44년 걸리는 계산 3개월에 끝내
윌리엄 쿡 캐나다 워털루대 수학과 교수가 한국에 있는 모든 술집 8만1998개를 걸어서 방문하는 최단 거리를 계산했다. 사진은 쿡 교수의 연구에 따른 최단 거리 경로를 나타낸다. 윌리엄 쿡 교수 제공
광고 로드중
미국 유명 수학자가 한국에 있는 모든 술집 8만1998개를 걸어서 방문하는 최단 거리를 계산했다. 쉬지 않고 모든 술집을 걸어서 방문하면 178일 1시간 56분 17초가 걸린다.
윌리엄 쿡 캐나다 워털루대 수학과 교수는 이달 8일(현지 시간) 모든 한국 술집 8만1998개를 걸어서 방문하는 최단 경로를 계산하고 증명한 결과를 자신의 홈페이지에 공개했다. 쿡 교수는 조합론과 최적화 분야에서 세계적인 수학자다.
쿡 교수는 ‘외판원 문제(TSP)’라고 불리는 유명한 수학 문제를 도로에서 최적의 경로를 찾는 문제에 적용했다. 외판원 문제란 도시가 여러 개 있을 때 외판원이 모든 도시를 한 번만 지나가면서 전부 방문할 수 있는 가장 짧은 거리를 구하는 문제다. 방문하는 도시의 수가 같더라도 각 도시를 연결하는 경로가 다르고 가장 짧은 거리를 찾아야 하기 때문에 무엇을 대상으로 하느냐에 따라 완전히 다른 문제가 된다.
광고 로드중
쿡 교수는 술집 8만1998개를 이용해 술집 2개씩을 붙여 한 쌍을 만드는 작업을 했다. 술집은 중복으로 등장할 수 있다. 총 33억6179만5003개 쌍이 나왔다. 쿡 교수는 최단 거리를 계산해 주는 공개 시스템인 ‘오픈소스라우팅 머신(OSRM)’을 이용해 각 쌍에 묶인 2개 술집을 서로 걸어서 잇는 최단 거리를 계산했다.
쿡 교수는 방대한 최단 거리 데이터를 조합해 ‘분기한정법(branch and bound)’으로 최적의 경로를 찾아냈다. 분기한정법이란 최적의 답이 될 만한 후보를 나뭇가지처럼 늘어놓고 답이 될 가망이 없는 것들은 가차 없이 잘라버리는 방법이다. 답이 나올 수 있는 범위를 정해두고 범위를 벗어나는 값들을 지워 계산의 양을 줄일 수 있다.
쿡 교수는 3개월에 걸쳐 여러 대의 컴퓨터를 병렬로 이용해 한국 술집 8만1998개를 걸어서 방문하는 최단 경로를 찾아냈다. 병렬로 연결된 각 컴퓨터가 문제를 푸는 데 사용한 시간을 모두 합하면 총 44년이다. 결과에 따르면 최단 경로에 소요되는 시간은 178일 1시간 56분 17초다. 연구 논문은 연말에 나올 예정이다.
쿡 교수는 “이번 문제를 2121개의 하위 문제로 바꿔 계산하는 양을 줄이는 수학적 아이디어로 해결했다”며 “외판원 문제를 길에서 여러 장소를 방문하는 최단 경로를 찾는 문제에 적용한 사례 중 가장 많은 수의 장소를 계산한 것”이라고 말했다. 직전 최고 기록은 2021년 네덜란드의 5만7912개 기념물을 방문하는 연구 결과다.
광고 로드중
외판원 문제는 수학 문제이지만 실생활을 비롯해 산업계 전반에 적용되고 있다. 택배 물품을 전달하는 최적의 경로, 반도체 기판을 만드는 방법 등에 외판원 문제가 사용된다. 엄 CI는 “외판원 문제를 우주의 수많은 별을 방문하는 최단 경로를 계산하는 데도 적용할 수 있다”며 “외판원 문제에서 방문 대상 숫자를 높이면 최적화를 할 수 있는 새로운 수학적 아이디어를 생각해 낼 수 있다는 의미가 있다”고 말했다.
이채린 동아사이언스 기자 rini113@donga.com