d라이브러리

여기서 문득 방문하고 싶은 도시가 10만 개라면 어떻게 해야 할 지 궁금해졌습니다. 지금까지 최고 기록은 8만 5900개 도시를 방문하는 거였으니까요.

n개의 도시를 여행하는 외판원 문제는 ‘NP-완전’이에요. 어쩌면 n의 다항식 꼴로 표현되는 특정 횟수(다항 시간) 안에 풀 수 있는 방법이 없을 수도 있지요. 밀레니엄 문제 중 하나가 ‘P대 NP’인데 대부분의 수학자가 P≠NP로 여기고 있거든요. P는 다항 시간 안에 해결 가능한 문제, NP는 답이 맞았는지 확인하는 게 다항 시간 안에 해결 가능한 문제를 말해요.

따라서 학자들은 효율적인 대안으로 근삿값을 구하는 알고리듬 연구를 하고 있습니다. 가장 최적인 답을 몰라도 비교적 빠른 시간에 최적의 답에 어느 정도 가까운 근사 해를 계산할 수 있다는 것이지요. 

지금까지 찾은 근사 알고리듬 중에 가장 답에 근접한 해를 구해 주는 건 니코스 크리스토피데스가 1976년에 개발한 ‘크리스토피데스 알고리듬’이에요. 2011년 미국 스탠퍼드대학교와 캐나다 맥길대학교 공동연구팀은 이 알고리듬을 이용해 어떤 두 도시 사이를 왕복하는 비용이 같을 때 최저 값보다 약 1.49배 비싼 경로를 찾았습니다. 

갈 때 다르고 올 때 다른 경우는?
 

그런데 현실에서는 두 지점을 오갈 때 드는 비용이 다른 경우도 있습니다. 상행선과 하행선의 열차 개수와 시간도 다르며 길의 지형이나 도로 상황도 다르기 때문이지요. 

그래서 여행하는 외판원 문제는 오갈 때 비용이 같다고 가정하는 대칭적인 경우와 비용이 달라지는 비대칭적인 경우로 나눠서 연구합니다. 대칭적일 때보다 비대칭적일 때 문제는 훨씬 더 어려워집니다. 이런 문제를 근사적으로나마 풀 수 있는 알고리듬이 있는지 조차 미지수였지요.

그런데 2017년 11월 올라 스벤손 스위스 로잔 연방공과대학교 교수팀은 근사 알고리듬 분야에서 획기적인 발견을 했습니다. 여행하는 외판원 문제의 비대칭 상황에서 근사 알고리듬을 만든 것이지요. 스벤손 교수팀은 최적 해의 5500배 비용이 드는 알고리듬을 만들었습니다. 즉 어떤 도시들을 도는 데 최저 비용의 5500배 이내로 도는 방법을 빠르게 찾을 수 있는 효율적인 알고리듬을 만든 거예요!