[외판원 문제 / TSP] 메트릭 & 2-근사 (Metricity & 2-Approximation)

안녕하세요. 이번에는 traveling salesman problem에 대해서 알아보도록 하겠습니다. 주로 줄여서 TSP라고도 부르며, 제가 알기로 우리말로는 외판원 문제로 불립니다. 개괄적인 설명은 이전 글에서 했습니다.

2019/07/10 - [근사 알고리즘] - 근사 알고리즘

근사 알고리즘 (Approximation Algorithm)

그러니 이번에는 서두 없이 바로 문제를 정의해 보도록 하겠습니다. 문제의 입력으로 지점들의 집합 \(V\)와 모든 지점 쌍 \(u\), \(v\)에 대해서 거리 \(d(u, v)\)가 주어집니다. 우리의 목표는 한 지점에서 시작해서 모든 지점들을 정확히 한 번씩만 거쳐서 시작 지점으로 돌아오는 방법 중 가장 거리가 짧은 것을 찾는 것입니다. 참고로, 시작 지점을 굳이 입력으로 받을 필요는 없습니다. 어차피 모든 지점을 한 번씩만 지나야 하기 때문에 어디에서 시작하나 optimal solution의 차이는 없습니다.

 

당장 TSP는 유명한 \(\mathsf{NP}\)-난해 (\(\mathsf{NP}\)-hard) 문제 중 하나입니다. 따라서 다항 시간에 효율적으로 optimal solution을 찾는 것은 \(\mathsf{P} \neq \mathsf{NP}\)인 한 불가능합니다. 그러면 이를 근사적으로 해결하는 방법을 찾아야 할 것입니다. 하지만 불행히도 임의의 \(V\)와 \(d\)가 입력으로 주어졌을 때는 근사 알고리즘이 존재하지 않습니다.

 

간단히 이유를 알아보겠습니다. 일단, 잘 알려진 어려운 문제를 하나 가져오겠습니다. 어떤 그래프에서 모든 정점들을 정확히 한 번씩만 거치는 cycle을 Hamiltonian cycle이라고 합니다. 이때, 어떤 그래프 \(G\)에 Hamiltonain cycle이 존재하는지 판별하는 문제는 \(\mathsf{NP}\)-난해합니다. 그런데, 만약 TSP를 근사적으로 해결하는 \(\rho\)-근사 알고리즘이 존재한다면 (단, \(\rho < \infty\)), 우리는 이 문제를 다항 시간에 풀 수 있게 됩니다. 방법은 다음과 같습니다. 지점 \(V\)는 원래 그래프 \(G\)의 정점 \(V(G)\)를 그대로 가지고 옵니다. 거리는 간선이 존재하면 0, 존재하지 않으면 1로 설정합니다. 다시 말해,

\[d(u,v) = \left\{ \begin{array}{rl} 0, & \text{if } (u,v) \in E(G), \\ 1, & \text{if } (u,v) \notin E(G). \end{array} \right.\]

 

만약 원래 그래프 \(G\)에 Hamiltonian cycle이 존재하였다면, 우리가 만든 TSP의 입력에서 optimal solution의 거리의 합은 0이됩니다.  0에다가는 어떤 유한한 값 \(\rho\)를 곱해도 0입니다. 즉, \(\rho\)-근사 알고리즘은 항상 거리의 합이 0인 solution을 출력할 것이고, 이는 원래 그래프에서의 Hamiltonian cycle을 형성하게 됩니다. 반대로 원래 그래프에 Hamiltonian cycle이 존재하지 않았다면, 우리의 근사 알고리즘은 거리의 합이 0보다 큰 solution을 반환할 것입니다. 이를 통해서 원래 그래프에 Hamiltonian cycle이 처음부터 없었다는 사실을 판단할 수 있습니다. 게다가 근사 알고리즘의 정의에 의해서 위 과정을 모두 다항 시간에 처리할 수 있습니다. 따라서 이는 \(\mathsf{P} \neq \mathsf{NP}\)인 한 모순이 됩니다.

---

이전 글에서도 말씀드렸지만, 불가능하다고 해서 손을 놓고만 있기에는 영 찝찝하죠. 다른 수를 생각해봐야죠. 만약 문제에 합리적인 조건을 부가한다면, 문제가 좀 더 쉬워질 것이고 동시에 괜찮은 근사 알고리즘을 이끌어낼 수 있을 것입니다. 문제의 입력을 잘 살펴보겠습니다. 지점 집합 \(V\)에는 어떤 제약을 걸기 어려워 보입니다만 거리 \(d\)는 여러 가지를 할 수 있을 것으로 보입니다. 다음의 경우를 생각해 보죠. 여러분이 직장에서 집으로 돌아오는 길에 은행을 들렀다고 합시다. 그렇다면 직장에서 집으로 바로 오는 거리가 은행을 들렀다가 오는 거리보다 짧다고 가정해도 괜찮지 않을까요?

Triangle inequality를 나타내는 그림: \(d(a, b) \leq d(a, c) + d(c, b)\)

이를 토대로 \(d\)에 다음과 같은 조건을 걸어 보겠습니다.

1. \(d(u, v) = 0 \Longleftrightarrow u = v\);

2. 임의의 \(u\), \(v\)에 대해서, \(d(u, v) = d(v, u)\);

3. 임의의 \(u\), \(v\), \(w\)에 대해서, \( d(u, v) \leq d(u, w) + d(w, v)\).

1번 조건은 한 지점에서 다시 그 지점으로의 거리는 0이며 어떤 두 지점의 거리가 0이면 원래 두 지점은 같은 곳이었다는 것을 알려줍니다. 2번은 한 지점에서 다른 지점으로 가는 거리나 반대로 오는 거리나 동일하다는 것을 나타냅니다. 마지막으로 3번 조건은 앞에서 설명한대로 바로 가는 것이 다른 곳을 경유해서 가는 것보다 길지 않다는 것을 의미합니다. 이러한 조건을 만족하는 \(d\)를 \(V\)의 metric이라고 합니다. 참고로 3번 조건은 나중에 매우 요긴하게 사용됩니다. 우리는 이를 triangle inequality라고 부릅니다.

---

이제 입력으로 들어오는 거리 \(d\)가 metric이라고 가정하겠습니다. 일단 앞서 임의의 거리에 대해서 근사 알고리즘이 존재하지 않는다는 증명은 더 이상 들어맞지 않습니다. 왜냐하면 원래 그래프 \(G\)로부터 만든 \(d\)가 metric이라는 보장이 없기 때문입니다. 자, 그렇다면 이번에는 근사 알고리즘을 만들 수 있을까요? 기쁘게도, 가능합니다! 그리고, 방법 또한 매우 간단합니다. 그 방법을 예시와 함께 소개해 드리도록 하겠습니다.

Traveling salesman problem 입력 예시 - \(V\)는 원, \(d\)는 지점 사이의 직선 거리

제가 만든 예시는 위 그림과 같습니다. 지점은 원으로 표시하였으며 거리는 두 지점 사이의  직선 거리(즉, Euclidean distance)입니다.

 

지금부터 TSP의 입력을 cost가 \(d\)인 weighted complete graph라고 생각하겠습니다. 모든 지점을 한 번씩만 지나는 방법은 결국 이 그래프에서의 Hamiltonian cycle에 대응하며, 우리의 목표는 cost가 가장 적은 Hamiltonian cycle을 찾는 것입니다. 물론 바로 구하는 것은 힘드므로 다른 방법을 생각해야 합니다. 이를 위해서는 Hamiltonian cycle의 성질을 파헤쳐 볼 필요가 있습니다. 잘 생각해 보면 두 가지 재미있는 성질을 발견할 수 있습니다. 첫 번째는 connected하다는 점입니다. 즉, cycle 상에서 어느 한 정점에서 다른 정점으로 갈 수 있는 방법이 존재한다는 의미입니다. 두 번째는 spanning하다는 점입니다. 이는 그래프의 모든 정점을 포함한다는 것을 알려줍니다.

 

자, 어떤 그래프에서 connected하면서 spanning한 성질을 만족하는 것이 또 무엇이 있을까요? 자료 구조를 공부한 분이라면 아마도 이것을 떠올리실 것이라고 생각합니다. 네, 바로 spanning tree입니다. 이는 우리를 많이 도와줄 수 있을 것으로 보입니다. 왜냐하면 우리는 spanning tree 중에서 cost가 가장 작은 것, 즉 minimum cost spanning tree(MST)를 다항 시간에 찾는 여러 효율적인 알고리즘들을 많이 배웠기 때문입니다. 우리의 목표가 minimum cost Hamiltonian cycle을 찾는 것이니 MST를 활용한다면 그렇게 비싸지 않은 Hamiltonian cycle을 얻을 수 있을 것입니다.

 

Minimum cost spanning tree 예시

그러면, 위와 같이 MST를 하나 가지고 옵시다. 이제 어떤 작업을 해 주어야 적절한 Hamiltonian cycle을 구할 수 있을까요? 여기서는 Hamiltonian cycle과 매우 비슷한 친구를 가져오려고 합니다. 눈치를 채신 분들도 계실 것입니다. 바로 Eulerian circuit입니다. 우리에게는 '한붓그리기'로 더욱 친숙한 개념입니다. 이는 한 정점에서 시작해서 모든 간선을 정확히 한 번씩만 거쳐서 다시 시작 정점으로 돌아오는 circuit을 말합니다. 어릴 때 우리는 Eulerian circuit이 존재하기 위한 필요충분조건을 배웠습니다.

Eulerian circuit

---

그래프의 모든 정점의 차수(degree)가 짝수일 때, 그 그래프 위에 Eulerian circuit이 존재한다. 또한, Eulerian circuit을 다항 시간에 찾는 알고리즘도 존재한다.

Eulerian circuit을 찾는 방법은 나중에 따로 적어보도록 하겠습니다. 간단히 방법을 말씀드리면, 아직 방문하지 않은 정점 하나를 잡고 이를 지나는 cycle을 계속 찾아나가면 됩니다.

 

과연 MST에서 Eulerian circuit을 어떻게 찾는다는 것일까요? 방법은 매우 간단합니다. 모든 정점의 차수가 짝수여야 하니, 그냥 MST의 모든 간선을 한 개씩 더 복제하는 거죠. 그러면 자명하게도 모든 정점의 차수가 짝수가 될 것입니다.

MST의 간선이 한 개씩 복제가 된 모습

위 사진처럼 얻어진 multigraph에 대해서 다음과 같이 Eulerian circuit을 얻을 수 있습니다.

얻어진 Eulerian circuit

예시 그림에서 얻은 Eulerian circuit \(C\)는 다음과 같습니다.

\[ C = a, b, f, e, f, c, g, h, g, c, d, c, f, b, a\]

 

이 Eulerian circuit을 이용해서 Hamiltonian cycle을 만들어보고자 합니다. 방법은 간단합니다. 구한 Eulerian circuit을 그대로 따라가기만 하면 됩니다. 시작점을 \(a\)라고 하겠습니다.

정점 \(a\)를 방문한 모습

Eulerian circuit \(C\)에 따르면, 다음에 방문한 정점은 \(b\)입니다. 아직 우리는 \(b\)를 방문하지 않았으므로 방문해줍니다.

정점 \(b\)를 방문한 모습

다음은 \(f\)의 차례입니다. 아직 \(f\)를 방문하지 않았으므로 방문합니다. 그러고 나서는 \(e\)를 방문해야 하며, 똑같이 \(e\)도 아직 들른 적이 없으므로 방문합니다.

정점 \(f\)와 \(e\)를 차례로 방문한 모습

이제 문제가 발생합니다. Circuit \(C\)에 따르면 다음에 방문할 정점은 \(f\)입니다. 하지만 우리는 이미 \(f\)를 방문했습니다. 어떻게 하면 좋을까요? 네, 그냥 건너 뛰는 것입니다. \(C\)에 따르면 그다음에 방문할 정점은 \(c\)입니다. 따라서 바로 \(c\)로 가는 것이죠.

정점 \(e\)에서 바로 정점 \(c\)로 방문한 모습

우리는 이러한 작업을 shortcutting이라고 합니다. 나중에 엄밀히 말씀드리겠지만, 이 작업이 허용되는 이유는 주어진 거리 \(d\)가 metric이기 때문입니다. 즉, 정점 \(e\)에서 정점 \(c\)로 곧장 가는 것이 \(f\)를 경유하는 것보다 이득이라는 뜻입니다. 따라서 이런 방식으로 얻은 Hamiltonian cycle이 기존의 Eulerian circuit보다 더 좋기만 할 것입니다.

 

계속 \(C\)를 따라가도록 하겠습니다. 다음 방문할 정점 \(g\)와 \(h\)는 각각 처음 방문하는 것이므로 바로 방문해 줍니다.

정점 \(g\)와 \(h\)를 방문한 모습

다시 동일한 문제가 발생하였습니다. \(C\)에 따르면, 다음에 방문할 정점은 \(g\)인데 이미 방문을 해 버렸습니다. 그 다음 \(c\)도 이미 방문을 한 상태입니다. 그렇다면 자연스럽게 그다음 정점인 \(d\)로 shortcut합니다. (지금 보니 정점 \(d\)와 거리 \(d\)가 같은 이름으로 쓰였군요. 혼란을 드려 죄송합니다. 흐엉)

정점 \(d\)로 바로 방문한 모습

마지막으로 \(C\)에 남은 \(c\), \(f\), \(b\) 모두 방문을 한 정점들이기 때문에 시작 정점 \(a\)로 바로 shortcut합니다. 그러면 다음 그림과 같은 Hamiltonian cycle을 얻을 수 있게 됩니다.

최종 결과

---

알고리즘에 대한 설명이 모두 끝났습니다. 이를 정리하면 다음과 같습니다.

A 2-approximation algorithm for TSP

---

입력: 지점 \(V\), metric \(d: V \times V \rightarrow \mathbb{Q}_+\)

출력: 모든 정점을 한 번씩 지나는 cycle

 

1. \(V\)를 정점으로 하고 간선의 cost가 \(d\)인 complete graph에 대해 minimum spanning tree \(T\)를 구한다.
2. \(T\)의 모든 간선을 한 개씩 더 복제한 multigraph \(S\)를 만든다.
3. \(S\) 위의 Eulerian circuit \(C\)를 구한다.
4. \(C\)를 따라 정점을 하나씩 방문하며 만약 이미 방문한 정점이면 shortcut한다.

일단 이 알고리즘이 다항 시간에 동작한다는 것은 쉽게 알 수 있습니다. 1번 단계에서 MST를 구하는 방법은 매우 잘 알려져 있습니다. 3번 단계는 완벽히 설명하지는 않았습니다만 다항 시간에 구할 수 있습니다. (검색해 보니 우리말로 된 자료가 많이  있더군요!) 마지막으로 4번 단계도 \(C\)의 간선들을 한 번씩 방문하는 것이므로 \(O(E(S))\)에 진행할 수 있습니다.

 

이제 이 알고리즘이 출력하는 solution이 그리 나쁘지 않은 solution이라는 것을 증명해 보겠습니다. 우리 알고리즘이 준 cycle을 \(H\), optimal cycle을 \(H^\star\)라고 하겠습니다. 또, 어떤 간선의 집합 \(F\)에 대해서, 그 간선의 거리의 합을 \(d(F)\)라고 하겠습니다. 제가 보이려고 하는 것은 다음과 같습니다.

\[ d(H) \leq 2 d(H^\star) \tag{1} \]

그러면 이 알고리즘이 2-근사 알고리즘이라는 것을 알 수 있습니다.

 

차근히 살펴보도록 하죠. 먼저 입력에서 \(d\)가 음수가 아닌 값을 가진다는 것을 확인하시기 바랍니다. 이는 위의 metric 정의에서는 나타나지 않지만, metric의 조건들을 사용하면 쉽게 모든 거리가 0보다 크거나 같아야 한다는 사실을 얻을 수 있습니다. (직접 증명해 보시기 바랍니다.)

 

알고리즘의 1번 단계에서는 MST를 구하였습니다. 한 가지 유용한 사실은 Hamiltonian cycle에서 간선 하나를 지우면 spanning tree를 얻게 된다는 점입니다. 앞에서 우리는 \(d\)가 항상 0보다 크거나 같다고 하였습니다. 그러므로 optimal solution \(H^\star\) 위의 어떤 간선 \(e\)에 대해서 다음과 같은 사실을 이끌어 낼 수 있습니다.

\[ d(H^\star) \geq d(H^\star - e) \geq d(T) \tag{2} \]

두 번째 부등식은 \(T\)가 MST이기 때문에 성립합니다.

 

2번과 3번 단계에서는 \(T\)의 모든 간선을 한 개씩 더 복제하여 \(S\)를 만들고 이 위의 모든 간선을 정확히 한 번씩 지나는 Eulerian circuit \(C\)를 구합니다. 따라서 \(C\)의 cost의 합은 정확히 \(T\)의 두 배가 됩니다.

\[ d(C) = 2 d(T) \tag{3} \]

 

마지막으로 4번 단계에서는 \(C\)를 shortcut하여 \(H\)를 만듭니다. 일단 만들어진 \(H\)가 모든 정점을 한 번씩만 지나는 cycle이라는 점은 명확합니다. \(T\)가 spanning한다는 성질을 통해서 주어지는 모든 정점들을 지나게 될 것이라는 점을 알 수 있으며, \(T\)가 connected하고 \(C\)가 모든 간선을 한 번씩 지난다는 점을 통해서 모든 정점들을 최소한 한 번은 지나게 될 것이라는 점도 알 수 있습니다. 마지막으로 shortcutting을 통해서 모든 정점을 정확히 한 번씩만 지나게 된다는 것도 이끌어 낼 수 있습니다. 게다가, 앞서 논의한 대로, \(d\)는 triangle inequality를 만족하기 때문에 shortcutting이 cost를 늘리지 않는다는 점도 확인할 수 있습니다. 따라서,

\[ d(H) \leq d(C) \tag{4} \]

가 됩니다.

 

이것으로 모두 끝났습니다. 식 (2), (3), (4)를 모두 조합하면 식 (1)을 얻을 수 있습니다. 이로써 우리 알고리즘이 2-근사 알고리즘이라는 것을 증명하였습니다. :)

---

이제 컴퓨터 과학의 숙명과도 같은 질문을 꺼내어 들 차례입니다. 과연 더 잘할 수 있을까요? 그전에 무엇을 더 잘해야 할까요? 일반적인 알고리즘이라면 대개의 경우 시간 복잡도가 주요한 척도입니다. 물론 임베디드 시스템과 같이 메모리 공간이 희소한 상황이라면 공간을 효율적으로 관리하는 것 또한 중요합니다. 하지만, 근사 알고리즘의 세계에서는 이들이 크게 작용하지 않습니다. 왜냐면 대개의 경우 풀고자 하는 문제들이 이미 너무 어려워서 optimal solution을 찾는 것을 포기한 상황이기 때문입니다. (항상 그런 것은 아닙니다. 다항 시간에 풀리는 문제라도 시간 복잡도가 너무 커서 훨씬 빠른 시간에 근사적으로 푸는  방법을 찾는 경우도 있습니다.)

 

따라서 근사비(approximation ratio)를 낮추는 데에 초점이 맞추어져 있습니다. 과연 이 문제에 대해서 2보다 작은 근사비를 가지는 알고리즘을 만들 수 있을까요? 네, 가능합니다. 1976년 Nicos Christofides가 TSP를 해결하는 1.5-근사 알고리즘을 제시하였습니다. 방법은 오늘 소개해 드린 알고리즘과 비슷합니다. 대신, Eulerian circuit을 찾기 위해서 굳이 MST의 모든 간선을 복제하지 않습니다. 사실 모든 간선을 복제하는 것은 좀 멍청하기는 했습니다. 과연 어떻게 하면 될까요? 이는 다음에 포스팅하도록 하겠습니다.

 

감사합니다. :)