[사이언스리뷰] 응용수학자의 ‘외판원 순회 난제’

컴퓨터 기술 발달로 최적해 찾아
지식 분야의 통합, 난제해결 첫발

수학은 노벨상 분야가 아니라 그런지 관련 연구가 사람들의 이목을 집중시키는 경우가 별로 없다. 그러나 응용수학자들이 연구하는 것 중 ‘외판원 문제(Traveling Salesman Problem·TSP)’는 현실 세계에서도 아주 유용한 것으로 뉴욕타임스 1면에 두 번이나 보도됐다.

외판원 문제를 쉽게 설명하면 방문영업을 하는 외판사원이 우리나라의 8개 특별·광역시의 각 도시를 한 번씩만 방문하고 출발한 도시로 되돌아오려면 어떤 순서로 방문하는 것이 가장 짧은 여행 경로를 갖느냐는 것이다.

외판원 문제는 단순히 도시를 방문하는 지리적 문제로만 응용되지 않는다. 물류산업에서의 배차, 항공기 스케줄링, 반도체 설계, 드릴머신 배치 등은 물론 게놈정보 분석, 천체망원경 배치, 엑스선 결정학 등에서도 사용되고 있다. 따라서 수많은 수학자, 컴퓨터과학자. 산업공학자, 경영과학자들이 수학적 성질, 컴퓨터 알고리즘·데이터 구조 연구, 소프트웨어 개발, 산업·경영 문제 응용 등을 위해 연구하고 있다.

외판원 문제의 해결책을 단순히 접근하면 가능한 모든 길을 나열하되 경로 중 가장 짧은 길을 선택하면 된다. 하지만 이런 나열식 방법은 8개 도시도 가능 경로가 2520개나 되고, 도시 수가 24개만 돼도 가능한 모든 경로의 수는 9407경3336조개나 된다. 만일 초당 1000억번의 연산을 수행하는 최신형 PC를 사용해 24개 도시의 가능한 모든 경로 수를 나열하는 데에만도 30년이나 걸릴 것이다.

이희상 성균관대 교수·기술경영학

물론 과학자들은 단순한 나열과 비교보다는 훨씬 효율적인 방법을 연구한다. 그러나 외판원 문제는 8개 도시의 길을 사용해 서울에서 부산까지 가장 짧은 길을 찾는 최단거리 문제보다는 어렵다. 최단거리의 경우는 도시 수가 100개, 1000개로 증가해도 최단거리를 찾는 데 걸리는 계산 속도가 빠르게 증가하지 않으므로 최단 경로를 거의 모든 경우 정확히 찾을 수 있다. 반면 외판원 문제의 경우 도시 개수가 증가함에 따라 계산량이 기하급수적으로 증가할 수 있어 큰 문제의 경우 근사해를 찾는 데 만족해야 할 때도 많았었다.

외판원 문제는 1930년대부터 연구가 시작됐지만 1954년 미국 랜드연구소의 과학자들이 49개 도시의 최단거리를 찾아낸 이래로 최적을 찾을 수 있는 도시 수가 1971년 57개, 1964년 120개, 1980년 318개, 1987년 666개로 느린 발전이 진행돼 왔다. 1980년대로 접어들면서 세상에 존재하는 많은 수학적, 계산학적 문제의 상당수가 비슷한 정도의 복잡도가 있으며, 외판원 같은 문제는 난제 중 하나라는 것이 증명된 게 이 문제를 이해하는 데 큰 도움이 됐다.

반면 1980년 중반 다면조합(Polyhedral Combinatorics)이란 수학적 성취와 컴퓨터과학의 신기술, 경영 및 산업에 대한 축적된 응용 경험 등을 기반으로 외판원 문제의 최적화 가능한 문제 크기는 발전한다. 즉, 1987년 2392개, 2000년 5915개, 2004년 2만4978개 도시를 거쳐 2006년에 8만5900개 도시 문제가 가장 큰 크기의 최적해를 찾은 문제가 됐다.

과학자들은 최근 10년간 인류가 거주하고 있는 거의 모든 마을 규모인 190만 4711개 도시의 외판원 문제에 도전하고 있다. 외판원 문제는 최적해가 입증되지 못한 근사해도 최적해보다 얼마 이상 나쁘지는 않다는 갭(gap)을 구할 수 있는 문제이다. 190만4711개 도시 문제에 대해 2001년 0.5% 정도의 근사해의 갭이 올 1월엔 0.0474%까지 줄어들었으니 조만간 글로벌 규모의 도시를 모두 방문하는 외판원 문제의 최적해가 구해질 수도 있을 것 같다.

외판원 문제가 해결돼가는 과정에 수학, 컴퓨터과학, 산업공학, 경영과학 등 각 분야의 최상의 지식이 하나씩 더해지며 가능했던 것을 반추해보면, 세계 최고 수준의 과학연구란 단순한 아이디어를 발전시키거나 피상적 결합 이상의 헌신적 노력과 ‘통섭’(consilience·지식을 통합함)을 통해야 가능하다고 생각된다.

이희상 성균관대 교수·기술경영학