한 외판원이 n개의 도시를 돌아다니며 상품을 판매하려고 한다. 도시들 사이에는 도로가 있고, 각 도로는 돈, 체력, 연료, 시간 등 어떤 식으로든 비용을 요구하며, 외판원은 도로에 비용을 지불하면서 n개의 도시를 최소 한번씩 방문하고 시작 지점으로 돌아오려고 한다. 아마 서너개의 도시만 방문하면 될때는 외판원은 큰 고민 없이 도시 방문을 마쳤을 것이다. 그러나 그가 방문해야할 도시의 수가 늘어나면, 그는 고민에 빠지게 된다. 최소한의 비용을 내기 위해 도시를 어떤 순서로 방문해야 할까? 그 순서를 찾는 일반적인 방법은 있을까?
외판원 문제
이 외판원의 고민은 외판원 문제, 혹은 traveling salesman problem (TSP) 라고 불리는 난제이다. 이 문제에서 다루는 것은 도시를 방문하는 외판원이지만, 실제로 다양한 산업 분야에서 유용하게 다뤄진다. 직관적으로 유사해 보이는 항공기 스케줄링, 사물 배치부터 반도체 설계, 게놈정보 분석 등 여러 응용분야에서도 외판원 문제는 중요하게 여겨진다고 한다.
다시 문제로 돌아와서, 우리가 알고자 하는 것을 다시 풀어 써보면 다음과 같다.
모든 정점이 연결되어 있고, 각 간선에 비용이 부여된 그래프를 생각하자. 한 정점에서 출발해 다른 모든 정점을 거쳐 다시 원래의 정점으로 돌아오는 최소 비용의 순환 경로를 어떻게 찾을 수 있는가?
최소 비용의 경로를 찾는 방법
당연한 말이지만, 최소 비용의 순환경로는 당연히 존재한다. 정점의 개수가 엄청나게 많고 거기에 팩토리얼을 취하면 훨씬 더 많아지겠지만, 그래도 그 개수는 여전히 유한하기 때문이다. 이런 생각에서 착안하여, 약간은 멍청해보이지만 그래도 답이 있기는 한 해법을 하나 만들어볼 수 있겠다. 브루트포스(brute-force) 방법은 있을 수 있는 모든 경로를 다 계산해보고 그 중에 최소 비용의 경로를 뽑아내는 방법이다. 직관적이지만 이 방법의 시간복잡도는 O(n!)이고, 당연히 사용할 가치가 없는 방법이다. 그러면 조금 더 효율적인 알고리즘은 없을까?
동적계획법(dynamic programming)은 재귀함수와 메모를 사용하여 더 적은 정점을 가진 그래프에서 얻어낸 최소비용 경로로부터 더 많은 정점을 가진 그래프의 최소비용 경로를 유도해낸다. 개략적으로 설명하자면 다음과 같다. 만약 a에서 출발해 b로 가는 최소비용을 알고싶다면, b에 인접한 임의의 정점 c에 대해 (a에서 c로 가는 최소비용)+(c에서 b로 가는 비용)을 계산하고 그것이 최소가 되는 c를 찾아 최소비용 경로를 만드는 것이다. a에서 c로 가는 경로를 k-1 길이 경로, a에서 b로 가는 경로를 k 길이 경로라고 본다면 이것은 k 경로의 최소비용을 이미 아는 k-1 경로의 최소비용으로부터 귀납적으로 얻어내는 과정이라고 설명할수도 있다. 어쨌거나, 이 방법의 시간복잡도는 O((n^2)(2^n))으로, 줄어들기는 했지만 여전히 지수 시간이기 때문에 사용가치가 있다고 보기는 힘들다.
분기한정법(branch and bound)은 출발 정점에서부터 경로를 그리면서 분기를 만날때마다 어느 방향으로 가는 것이 더 최소비용이 될 가능성이 높은지를 판별하여, 더 '유망한' 방향을 먼저 탐색하는 방법이다.
외판원 문제에 적용할 경우 어느쪽이 유망한지를 판별하는 기준은 특정한 방향으로 갔을 때의 비용의 하한(lower bound)이다. 분기를 만날 때마다 각 방향의 비용의 하한을 계산한 후 하한이 작은 방향을 먼저 가보는 것이다. 안타깝게도 분기한정법의 시간복잡도 역시 지수 시간 아래로 내려가지 못한다.
이쯤되면 궁금한 것이 생긴다. 과연 외판원 문제를 다항시간 내에 해결할 방법은 존재할까? 사실 이것은 유명한 NP 완전 문제의 한 예시로, 만약에 P=NP라면 다항시간 내에 해결할 방법이 존재한다. 하지만 지금의 지식으로는 아무것도 알 수 없다. P≠NP여서 그런 해결법은 없을거라는 관점이 일반적이긴 하지만 아직은 존재한다는 것이 증명되지도 않았고, 존재하지 않는다는 것이 증명되지도 않았다.
‘더 정확하게’ 대신 ‘더 빠르게’
그렇다면 이번에는 조금 다르게 생각해보는건 어떨까? 우리는 지금까지 어떻게든 최적의 해를 찾아내려다가 시간이라는 것을 포기할 수 밖에 없었다. 그러면 이번엔, 시간을 보다 짧게하는 대신 최적을 포기해볼 수도 있지 않을까? 다시 말하면, 완벽한 해는 구하지 못하더라도 다항시간 내에 만족할만한 근사해를 구할 수 있지 않겠느냐는 것이다.
마치 할 수 있다는 듯이 말했지만, 사실 이마저도 쉽지 않다. 하지만, 조금의 조건을 더 추가한다면 약간의 만족스러운 결과가 얻어지기는 한다. 우리에게 필요한 조건은 간선을 지나가는 비용이 metric하다는 조건이다. metric은 직선거리를 생각하면 쉽게 떠올릴 수 있는 개념으로, 간단히 말하면 A에서 B로 곧바로 가는 것이 A에서 다른 여러 곳을 거친 후 B로 가는 것보다 비용이 덜 드는 성질이다. 이 조건이 있으면 우리는 불필요한 경유지를 건너뛰면서 이동하면 더 적은 비용의 경로를 만들 수 있다는 것을 이용할 수 있다.
실제로 이 조건 아래에서는 Christofides' Algorithm이라 불리는 1.5배 근사를 다항시간 내에 찾아낼 수 있다. 자세한 과정은 생략하겠으나, 근사의 아이디어를 써보면 다음과 같다.
1. 최소비용의 spanning tree (루프 없이 모든 정점을 연결시킨 것) 를 찾아 그린다.
2. 정점 사이에 최소한의 간선을 추가해 모든 정점이 짝수개의 선으로 연결되게 한다.
3. 간선을 따라 한붓그리기를 하여 정점을 모두 잇는다.
4. 한붓그리기를 따라 순환경로를 만들되, 이미 경유한 곳은 건너뛰며 이동한다.
순환경로에서 선 하나를 빼면 spanning tree가 된다는 것을 이용해 부등식을 세워주면 복잡하지 않은 과정으로 여기서 찾은 경로의 비용이 최소비용의 1.5배보다 작거나 같다는 것을 보일 수 있다. 설명없이 넘어가겠지만, 최소비용의 spanning tree는 다항시간 내에 찾을 수 있으므로 우리는 이 근사를 통해 꽤나 만족스러운 정확도와 시간을 획득했다고 할 수 있겠다.
남아있는 과제들
근사를 찾아냈다면, 그 다음에 꼭 필요한 질문은 '더 좋은 근사는 없는가?'이다. 사실 이건 매우 어려운 문제이며, Christofides' Algorithm이 나온지 무려 35년이 지난 2011년에야 샤안 오베이스 가람과 모힛 싱에 의해 1.44999999999999999999999999999999999999999999999999996배 근사가 발견되었다. 이 연구팀은 이 수치를 4/3까지 줄일 수 있을거라 추측했지만, 아직 더이상의 성과는 없는 것으로 알려져있다.
외판원 문제는 꽤나 간단하게 설명하고 이해하기도 쉬운 문제임에도 불구하고, 고도로 발전된 현대수학이 아직 이것을 완전히 해결하지 못했다는 것은 꽤나 흥미로운 사실이다. 게다가 2017년에 올라 스벤손, 야쿠프 타르나프스키, 리슬로 베그흐가 ‘오고 가는 방향에 따라 비용이 다른 경우’의 문제에서 5500배 근사를 발견하면서, 아직 해결해야할 문제가 매우 많다는 사실을 또 한번 상기시켜주었다. 과연 수학은 어디까지 도달할 수 있을지, 그리고 그 결과는 인류에게 어떤 도움을 줄 수 있을지 기대가 된다.
김태완 | Mathematics & Computer Sci. | 지식더하기
참고자료
[1] https://dl.dongascience.com/
[2] https://junstar92.tistory.com/
[3] https://gazelle-and-cs.tistory.com/
[4] https://terms.naver.com/
첨부 이미지 출처
[1] https://www.techenablement.com/
[2] https://raisonde.tistory.com/
[3] https://gazelle-and-cs.tistory.com/
