d라이브러리

우리는 밀레니엄 난제를 발표한 클레이 수학연구소를 가려고 미국을 여행지 목록에 넣었어요. 그런데 목적은 따로 있었지요. 사실 우린 야구로 뭉친 크루거든요. 미국하면 또 야구 아니겠습니까! 우리 같은 야구팬들은 미국 여행에서 이루고 싶은 목표가 하나 있습니다. 미국 30개 야구장에서 경기를 관람하고 오는 거지요. 최소 비용으로 모든 야구장을 방문하는 방법을 찾아볼까요?

야구장마다 경기가 있는 날과 경기 하는 시간이 정해져 있기 때문에 전통적인 외판원 문제로는 답을 찾을 수 없습니다. 

다행히도 외판원 문제를 연구하던 학자들은 실생활에 더 밀접하게 적용할 수 있게 외판원 문제를 응용해 연구했습니다. 그중 하나가 전통적인 외판원 문제에 ‘각 도시에서 외판원이 머물 수 있는 정해진 시간’을 요소로 추가한 것이 있지요. 

랍 프래트 SAS(미국 소프트웨어 회사) 연구원은 여행하는 야구팬 문제를 해결하기 위해 전통적인 외판원 문제에 ‘사건이 일어나는 시간’이 포함된 알고리듬을 이용했습니다. 각 경기장에서 경기가 있는 날과 경기 시간을 데이터로 이용했죠. 그 결과 24.8일 동안 약 4989km를 이동하는 경로가 최적의 답으로 나왔습니다.

그런데 놀랍게도 집념의 야구팬들이 이 어려운 일을 먼저 해냈습니다. 2008년 조시 로빈슨은 자동차로만 30곳의 야구장을 여행하는 일정을 짜서 26일 만에 마쳤습니다. 척 부스는 2012년 23일 만에 모든 경기장을 돌았지요. 정말 대단하죠?

미국은 우리나라와 다르게 땅이 어마어마하게 컸어요. 서쪽 끝에서 동쪽 끝으로 가려면 비행기로만 5시간 넘게 걸리지요. 또 경기를 하지 않는 날도 있고, 경기하는 시간이 정해져 있으니 동선을 짜기는 더 어렵습니다. 2015년 랍 프래트 SAS 연구원은 미국 전역에 걸쳐 있는 30개 야구장에 가서 경기를 보고 오는 문제를 풀었어요. 프래트 연구원은 미국 메이저 리그 2015년 6~7월 경기 일정을 토대로 다음과 같이 24.8일에 걸친 동선을 짰어요.