지난 포스팅에서 traveling salesman problem이 (우리말로 외판원 문제) 무엇인지 알아보았습니다. 안타깝게도 일반적인 거리에 대해서는 적절한 근사 알고리즘이 존재하기 어렵다는 것을 보였습니다. 하지만 metric인 경우에는 2-근사 알고리즘이 존재한다는 것을 보였습니다. 아직 보지 않으셨다면 다음 링크를 참조해 주세요. :)
[외판원 문제 / Traveling Salesman Problem] 메트릭 & 2-근사 (Metricity & 2-Approximation)
안녕하세요. 이번에는 traveling salesman problem에 대해서 알아보도록 하겠습니다. 주로 줄여서 TSP라고도 부르며, 제가 알기로 우리말로는 외판원 문제로 불립니다. 개괄적인 설명은 이전 글에서 했습니다. 201..
gazelle-and-cs.tistory.com
1976년 Nicos Chistofides는 일반적인 metric이 입력으로 주어지는 TSP에 대해서 1.5-근사 알고리즘을 제시하였습니다. 이번 포스팅에서는 그 알고리즘을 알아보도록 하겠습니다!
직관적으로 이해하기
저번 포스팅에서 소개한 알고리즘을 간단히 설명하겠습니다. 모든 지점을 한 번씩 방문하여 시작 지점으로 돌아오는 것은 그래프에서 Hamiltonian cycle에 대응합니다. Hamiltonian cycle은 그래프에 connected하며 spanning합니다. 이 성질을 모두 만족시키면서 우리에게 크게 도움이 된 것이 바로 spanning tree입니다. 우리의 목표가 minimum-cost Hamiltonian cycle을 찾는 것이므로 minimum-cost spanning tree(MST)를 대신 찾습니다. 얻은 MST의 모든 간선을 한 개씩 더 복제를 한다면, 그 위에 Eulerian circuit이 존재한다는 것을 알 수 있습니다. 마지막으로 그렇게 얻은 Eulerian circuit을 차례로 방문하며 만약 이미 방문을 한 경우라면 그다음 정점을 방문하는 방식으로 "shortcut"을 합니다. 이 shortcutting이 우리에게 도움이 된 이유는 입력으로 주어지는 거리가 metric이기 때문입니다.
오늘 말씀드릴 알고리즘도 비슷합니다. 똑같이 MST에서 시작하며, Eulerian circuit을 구한 후 shortcutting을 하는 방식입니다. 다른 점은 딱 하나입니다. 이전에는 MST 위에서 Eulerian circuit을 구하기 위해서 간선을 모두 한 개씩 복제하였습니다. 하지만 생각해 보면, 굳이 그럴 필요까지는 없습니다. Eulerian circuit이 존재하기 위한 필요충분조건은 모든 정점의 차수(degree)가 짝수인 것이기 때문입니다. 즉, MST 위에서 이미 짝수 차수를 갖는 경우라면, 굳이 이 정점에 손을 댈 필요가 없습니다. 예를 들어 다음과 같은 MST를 얻었다고 가정해 봅시다.
여기서 우리가 수정을 할 필요가 있는 정점은 아래 그림에서 빨간색으로 칠해진 정점들 뿐입니다.
빨간 정점 하나의 차수를 수정하기 위해서는 간선 하나로 충분합니다. 그렇다면 간선을 어떻게 추가해야 적은 비용으로 모든 정점의 차수를 짝수로 만들 수 있을까요?
네, 바로 빨간 정점들을 짝지어 주면 됩니다. 위 그림과 같이 초록색 점선으로 표현된 간선을 MST에 추가한다면 모든 정점의 차수가 짝수가 될 것입니다. 우리는 이런 형태의 간선 집합에게 이름을 붙여주었습니다. 바로 matching입니다. 게다가 빨간색 정점이 모두 matching에 참여를 하기 때문에 우리는 이를 perfect matching이라고 부릅니다. 예전에 matching과 관련된 글을 작성한 적이 있으니 잘 모르신다면 이를 참조하시기 바랍니다.
2019/01/28 - [조합론적 최적화/Bipartite matching] - 쾨니그의 정리 (Kőnig's Theorem)
쾨니그의 정리 (Kőnig's Theorem)
이 글은 홀의 정리 (Hall's Theorem) 밀접한 연관이 있습니다. 필요한 경우에는 이를 참조하세요. 2019/01/28 - [조합론적 최적화] - 홀의 정리 (Hall's Theorem) 무언가를 최적화시키는 문제를 보면 생각보다 많..
gazelle-and-cs.tistory.com
그중에서도 가장 거리가 짧은 perfect matching을 가지고 오겠습니다. 그러면 다음과 같은 multigraph를 얻게 됩니다.
이후의 과정은 저번 글과 동일합니다. 여기서 Eulerian circuit을 찾은 후에 이를 shortcut합니다.
알고리즘
앞에서 설명한 내용을 토대로 정확한 알고리즘을 적어보겠습니다.
Christofides algorithm
입력: 지점 \(V\), metric \(d: V \times V \rightarrow \mathbb{Q}_+\)
출력: 모든 지점을 정확히 한 번씩 지나는 cycle
- \(V\)를 정점으로 하고 간선의 cost가 \(d\)인 complete graph에 대해 minimum-cost spanning tree \(T\)를 구한다.
- \(T\) 위에서 홀수 차수를 갖는 정점들에 대해 minimum-cost perfect matching \(J\)를 구한다.
- \(T + J\) 위의 Eulerian circuit \(C\)를 구한다.
- \(C\)를 따라 정점을 하나씩 방문하며 만약 이미 방문한 정점이면 shortcut한다.
이전 글에서 보여드린 2-근사 알고리즘과 매우 흡사하죠? 그렇지만 놀랍게도, 이 알고리즘은 이전 알고리즘보다 좋은 1.5의 근사비를 가집니다. 어째서 더 좋아지는 것일까요? 당연히 minimum-cost perfect matching 때문일 것입니다. 그 외에는 이전 알고리즘과 달라진 것이 없기 때문입니다. Minimum-cost perfect matching이 어째서 더 좋은 근사비를 도출하는지 이제부터 차근히 알아가도록 하겠습니다.
Perfect matching의 존재 여부
하지만 그전에 짚고 넘어갈 부분이 있습니다. 바로, perfect matching이 정말로 존재하는지와 존재하더라도 이를 정말로 다항 시간에 찾을 수 있는지입니다. 여기서 뒤의 것은 증명을 생략하도록 하겠습니다. 정점의 개수가 짝수인 어떤 weighted graph에서 minimum-cost perfect matching을 찾는 것은 다항 시간에 가능합니다. 이렇게 넘어가기는 찝찝하지만 일단은 이를 받아들이고 넘어가도록 하겠습니다. 나중에 기회가 되면 꼭 포스팅하도록 하겠습니다.
대신 perfect matching이 항상 존재한다는 것은 쉽게 보일 수 있습니다. 그것이 존재하기 위해서는 짝지어 줄 정점이 짝수 개가 있으면 됩니다. 우리가 짝을 지을 정점은 MST 상에서 차수가 홀수인 정점들입니다. 과연 이 정점들이 짝수 개가 있을까요?
네, 그렇습니다. 사실 tree 뿐 아니라 임의의 undirected graph에서 차수가 홀수인 정점들의 개수는 항상 짝수 개입니다. 이는 유명한 '악수 정리(handshaking lemma)'를 통해서 증명할 수 있습니다.
악수 정리 (Handshaking lemma)
임의의 undirected graph에 대해서, 정점의 차수의 합은 간선의 개수의 2배와 같다. 다시 말해, 그래프 \(G = (V,E)\)가 주어졌을 때, \(\mathsf{deg}(v)\)를 정점 \(v\)의 차수라고 하면, 다음이 성립한다.
\[\sum_{v \in V} \mathsf{deg}(v) = 2 |E|\]
이런 정리를 어디선가 한 번 쯤은 보신 적이 있으리라 생각합니다. 증명은 매우 간단합니다. 간선 하나가 양 endpoint의 degree를 1씩 증가시키기 때문입니다. 위 정리를 통해 모든 정점의 차수의 합은 항상 짝수가 된다는 것을 알 수 있으며, 따라서 차수가 홀수인 정점들의 개수는 반드시 짝수 개여야 한다는 것을 보일 수 있습니다.
Perfect matching의 거리를 bound하기
근사 알고리즘에서 근사비를 보이기 위해서는 optimal solution을 적절하게 bound하는 것이 중요합니다. 실제로 이전 글의 2-근사 알고리즘에서는 minimum-cost Hamiltonian cycle의 거리를 minimum-cost spanning tree로 bound를 했기 때문에 얻을 수 있었습니다. 다시 말해, minimum-cost Hamiltonian cycle을 \(H^\star\), MST를 \(T\)라고 했을 때, \(d\)가 metric이라면 \(H^\star\) 위의 아무 간선 \(e\)에 대해서
\[d(H^\star) \geq d(H^\star - e) \geq d(T) \tag{1}\]
가 성립합니다. 첫 번째 부등식은 \(d\)의 값이 음이 아닌 수라는 성질 때문에 성립하며 두 번째는 Hamiltonian cycle에서 간선 하나를 제외하면 spanning tree가 되기 때문에 만족합니다. 이전 포스팅의 2-근사 알고리즘은 MST를 한 개 더 복제하여 거기서 얻은 Eulerian circuit \(C\)를 토대로 shortcut하여 Hamiltonian cycle \(H\)를 얻은 것이므로
\[d(H) \leq d(C) = 2 d(T) \leq 2 d(H^\star) \]
가 성립하였습니다.
이번에는 MST \(T\)와 함께 minimum-cost perfect matching \(J\)를 합쳤습니다. 즉, 다음과 같은 식이 성립하게 되겠죠.
\[d(H) \leq d(C) = d(T) + d(J)\]
이미 식 (1)을 통해서 \(d(T) \leq d(H^\star)\)라는 것을 알고 있습니다. 자연스럽게 남은 0.5는 \(J\)가 만족해 주어야 할 것입니다. 다시 말해서, 우리가 다음을 증명한다면, 이번 알고리즘의 근사비가 1.5가 된다는 것을 알 수 있습니다.
\[d(J) \leq \frac{1}{2} d(H^\star) \tag{2}\]
증명을 어떻게 할지를 개괄적으로 설명하겠습니다. 우리는 먼저 \(H^\star\)로부터 \(T\)에서 차수가 홀수인 정점들을 짝지은 perfect matching을 두 개 이끌어낼 것입니다. 특히, 각각을 \(J_1\), \(J_2\)라고 했을 때, 다음을 만족하도록 만들 것입니다.
\[d(J_1) + d(J_2) \leq d(H^\star) \tag{3}\]
여기까지 보일 수 있으면 나머지 증명은 간단합니다. 분명히 둘 중 하나는 \(d(H^\star)\)의 절반을 넘지 않을 것입니다. 근데 여기서 우리가 찾은 \(J\)는 \(T\) 위의 홀수 차수 정점에 대한 minimum-cost perfect matching이므로
\[ d(J) \leq \min \left\{ d(J_1), d(J_2) \right\} \leq \frac{1}{2} d(H^\star)\]
가 성립하게 됩니다. 따라서 식 (2)가 만족한다는 것을 알 수 있습니다.
이제 식 (3)을 만족하는 \(J_1\)과 \(J_2\)를 찾아보도록 하겠습니다. 이번에도 예시와 함께 설명을 드리겠습니다. 다음 그림을 optimal solution \(H^\star\)라고 하겠습니다. 이를 다항 시간에 구하는 것이 어려울 뿐이지 분명히 존재는 할 것입니다. 어차피 우리는 \(H^\star\)를 구하는 것이 아닙니다. 그저 여기에 식 (3)을 만족하는 perfect matching 두 개가 있다는 것만 보일 것입니다. 그러니 그냥 가져올 수 있습니다.
이때 빨간 정점은 MST \(T\)에서 홀수 차수를 가지던 것입니다. 지금부터 \(H^\star\)의 간선들을 두 개의 색으로 칠해보도록 하겠습니다. 먼저 정점 \(a\)에서 시작해서 \(H^\star\)를 따라가겠습니다. 다음 정점은 \(b\)입니다만 이는 빨간 정점이 아니므로 그냥 지나치도록 하겠습니다. 다음 정점은 \(c\)입니다. 정점 \(c\)는 빨간색이므로 여기서 멈추겠습니다. 지금까지 지나온 길을 다음과 같이 파란색 점선으로 칠하겠습니다.
이번에는 초록색 쇄선으로 간선을 칠하도록 하겠습니다. 정점 \(c\)의 다음은 \(d\)입니다. 이 정점도 똑같이 빨간색으로 칠해져 있으므로 다음 그림과 같이 간선을 칠한 후 여기서 끊어주도록 하겠습니다.
이제 어떤 패턴으로 \(H^\star\)를 칠하고 있는지를 이해하셨으리라 생각합니다. 한 빨간 정점에서 출발하여 \(H^\star\)를 따라 파란색 점선으로 간선을 칠하다가 다른 빨간 정점을 만나면 거기서부터는 초록색 쇄선으로 칠하는 것입니다. 반대로 초록색을 칠하다가도 빨간 정점을 마주하면 다시 파란색으로 칠하는 것이죠. 그러면 다음과 같이 칠해지게 됩니다.
여기서 우리는 \(H^\star\)가 파란색 점선과 초록색 쇄선으로 정확히 partition된다는 것을 확인할 수 있습니다. 이는 파란색 점선을 \(F_\mathsf{blue}\), 초록색 쇄선을 \(F_\mathsf{green}\)이라고 할 때,
\[ d(F_\mathsf{blue}) + d(F_\mathsf{green}) = d(H^\star) \tag{4} \]
가 된다는 사실을 의미합니다. 게다가 각각을 잘 살펴보면 빨간 정점 하나에서 출발해서 다른 빨간 정점 하나에서 끝나는 path들의 집합이라는 점도 알 수 있습니다. 각 path의 양 끝점을 다음 그림처럼 곧장 이어보겠습니다.
파란색 점선에서 \(a, b, c\)를 잇던 path를 \(a\)와 \(c\)를 곧장 잇는 간선으로 바꾸었습니다. 초록색 쇄선에서는 \(f, g, h\)가 \(f, h\)로 바뀌었습니다. 그러면 파란색 점선과 초록색 쇄선이 각각 빨간 정점들을 짝지어 주는 두 가지의 서로 다른 perfect matching이 된다는 것을 확인할 수 있습니다. 이를 각각 \(J_1\), \(J_2\)라고 하겠습니다. 여기서 우리는 \(d\)가 triangle inequality를 만족한다는 것을 알기 때문에
\[d(J_1) \leq d(F_\mathsf{blue}), \quad d(J_2) \leq d(F_\mathsf{green})\]
임을 이끌어낼 수 있습니다. 식 (4)와 위의 식을 통해 이렇게 구한 \(J_1\), \(J_2\)가 식 (3)을 만족한다는 사실을 알 수 있습니다. 이것으로 모든 증명이 마무리됩니다.
마치며
이번 포스팅에서 우리는 Christofides algorithm이 metric TSP를 푸는 1.5-근사 알고리즘이라는 점을 보였습니다. 과연 근사비를 가지는 알고리즘이 있을까요? 이 알고리즘이 1976년에 개발되었으니 자그마치 40년이 넘은 연로하신 알고리즘입니다. 하지만 아직까지 일반적인 metric을 입력으로 받는 TSP에 대해서 1.5보다 좋은 근사비를 가지는 알고리즘은 알려지지 않았습니다. 아마도 \( \frac{4}{3} \)까지는 낮출 수 있지 않을까하는 기대는 있습니다만, 현재까지 누구도 증명을 하지는 못하였습니다. 그나마 다행인 점은 일반적인 metric이 아닌 Euclidean distance와 같은 특수한 metric에서는 더 좋은 근사비를 가지는 알고리즘이 개발되었다는 것입니다. 하지만 이는 해당 metric의 성질을 십분 활용하여 얻은 결과이기 때문에 안타깝게도 일반적인 metric에 바로 적용하지는 못합니다.
그 때문에 TSP는 매우 유명한 (어쩌면 악명이 높은) 문제입니다. 따라서 여러 변형 문제들이 많이 존재합니다. 가장 유명한 변형 중 하나는 바로 path TSP입니다. 이름에서 유추할 수 있다시피 이 문제에서는 원래 TSP의 입력과 더불어 특별한 지점 두 곳이 추가적으로 입력으로 주어집니다. 바로 시작 지점과 도착 지점입니다. 즉, 시작 지점에서 출발하여 다른 모든 정점들을 정확히 한 번씩 거친 후에 도착 지점에 도달하는 방법 중에서 가장 거리가 짧은 것을 찾는 것입니다. (여기서도 여전히 거리는 metric입니다.)
이 문제도 Christofides algorithm으로 해결할 수 있습니다. 한붓그리기 조건 중에서 두 정점의 차수가 홀수이고 나머지 정점의 차수는 모두 짝수인 경우가 있습니다. 이때는 한 홀수 차수 정점에서 다른 홀수 차수 정점으로 모든 간선을 경유하여 도달하는 방법을 찾을 수 있습니다. 즉, minimum-cost spanning tree에서 이번에는 시작 지점과 도착 지점은 홀수로, 나머지 정점들은 짝수로 만드는 perfect matching을 찾는다면 위 알고리즘을 그대로 적용할 수 있습니다. (이때, 잘못된 차수를 가지는 정점의 개수는 여전히 짝수 개입니다.)
하지만 근사비가 달라지게 됩니다. 오히려 \( \frac{5}{3} \simeq 1.667\)로 나빠지게 됩니다. 이는 1991년 J. A. Hoogeveen에 의해서 증명이 되었습니다. 다음 포스팅에서는 어째서 이런 결과가 나타나게 되었는지를 알아보도록 하겠습니다.
고맙습니다. :)
'근사 알고리즘 > Traveling salesman' 카테고리의 다른 글
| 크리스토피데스 알고리즘으로 경로 외판원 문제 풀기 (Path TSP by Christofides' Algorithm) (0) | 2020.04.11 |
|---|---|
| [외판원 문제 / TSP] 메트릭 & 2-근사 (Metricity & 2-Approximation) (2) | 2019.07.20 |
