미국의 유명 수학자가 한국에 있는 모든 술집을 걸어서 방문하는 최단 거리를 계산해 낸 이색적인 연구 결과를 공개했다. 연구 논문은 연말에 나올 예정이다.

윌리엄 쿡 캐나다 워털루대 교수(수학과)는 지난 8일(현지 시각) 한국 술집 8만 1998개를 걸어서 방문하는 최단 경로를 계산한 결과를 자신의 누리집에 공개했다. 실제로 모든 술집을 쉬지 않고 걸어서 방문하면 178일 1시간 56분 17초가 걸린다.

쿡 교수는 조합론과 최적화 분야에서 세계적인 권위의 수학자다.

윌리엄 쿡 캐나다 워털루대 수학과 교수가 한국의 모든 술집(8만 1998개)을 걸어서 방문하는 최단 거리를 계산했다. 사진의 빨간 줄은 최단 경로를 표시한 것이다. 윌리엄 쿡 교수

쿡 교수는 과학기술정보통신부 산하 기초과학연구원(IBS)의 엄상일 이산수학그룹 CI(Chief Investigator)에게서 제공받은 한국 경찰청의 ‘전국 술집 위치정보’를 이용했다.

쿡 교수는 ‘외판원 문제(TSP)’라는 유명한 수학 문제를 최적의 경로를 찾는데 적용했다.

외판원 문제란 외판원이 여러 도시를 한 번 지나면서 모든 곳을 방문할 수 있는 가장 짧은 거리를 구하는 것이다. 각 도시를 연결하는 길(경로)은 달리 나 있어 방문하는 도시의 수가 같아도 가장 짧은 거리를 찾는 데는 어떤 길을 택하느냐에 달렸다.

외판원 문제는 수학 문제이지만 실생활을 비롯해 산업계 전반에 적용되고 있다. 택배 물품을 전달하는 최적의 경로, 반도체 기판을 만드는 방법 등에 사용된다.

엄 CI는 “외판원 문제를 우주의 수많은 별을 방문하는 최단 경로를 계산하는 데도 적용할 수 있다”며 “외판원 문제에서 방문 대상 숫자를 높이면 최적화를 할 수 있는 새로운 수학적 아이디어를 생각해 낼 수 있다는 의미가 있다”고 했다.

'전국 술집 위치정보'에 따르면, 2023년 기준으로 한국의 술집은 9만 680개다. 주소, 위도, 경도 등이 포함돼 있다.

쿡 교수는 같은 건물에 있는 여러 술집은 1개로 설정하는 등 데이터를 정리해 술집 수를 8만1998개로 정했다.

이어 이들 술집을 2개씩 붙여 한 쌍을 만들었다. 다만 술집은 중복될 수 있다.

이 결고, 총 33억 6179만 5003개 쌍이 나왔다.

쿡 교수는 최단 거리를 계산해 주는 공개 시스템인 ‘오픈소스라우팅 머신(OSRM)’을 이용해 각 쌍에 묶인 2개 술집을 서로 걸어서 잇는 최단 거리를 계산했다.

그는 방대한 최단 거리 데이터를 조합해 ‘분기한정법(branch and bound)’으로 최적의 경로를 찾아냈다. 분기한정법이란 최적의 답이 될만한 후보를 나뭇가지처럼 늘어놓고 답이 될 가망이 없는 것들은 잘라버리는 방법이다. 이는 정해진 범위를 벗어나는 값들을 지워 계산하는 양을 줄일 수 있다.

쿡 교수는 3개월 동안 여러 대의 컴퓨터를 병렬로 이용해 한국 술집 8만 1998개를 걸어서 방문하는 최단 경로를 찾아냈다.

병렬로 연결된 각 컴퓨터가 이를 푸는데 사용한 시간은 모두 44년이지만, 최단 경로에 소요되는 시간은 178일 1시간 56분 17초였다.

쿡 교수는 “이번 문제는 2121개의 하위 문제로 바꿔, 계산하는 양을 줄이는 수학적 아이디어로 해결했다”며 “외판원 문제를 길에서 최단 경로를 찾는 문제에 적용한 사례 중 가장 많은 수의 장소를 계산했다”고 말했다.

직전의 최고 기록은 2021년 네덜란드의 5만 7912개 기념물을 방문하는 연구 결과라고 소개했다.

쿡 교수는 “한국 술집 정보를 이용한 것은 한국 경찰청이 제공하는 데이터가 정확하고 방대했기 때문”이라고 말했다.

그는 지난해 IBS 방문을 앞두고 한국 학생들에게 할 강연을 준비하면서 이 문제에 도전하기 마음 먹었다고 했다.

기초과학연구원(IBS)의 엄 CI는 “술집 위치정보를 구매한 가격은 단돈 1000원”이라며 “이렇게 싼 값으로 훌륭한 수학 결과를 내는데 일조해 뿌듯하다”고 했다.