크리스토피데스 알고리즘으로 경로 외판원 문제 풀기 (Path TSP by Christofides' Algorithm)

오랜만에 근사 알고리즘으로 돌아왔습니다. 지난번 크리스토피데스 알고리즘(Christofides' algorithm)을 공부하면서 마지막에 외판원 문제(traveling salesman problem, TSP)의 변형인 경로 외판원 문제(path TSP)를 소개하면서 끝냈습니다.

2019/07/23 - [근사 알고리즘/Traveling salesman problem] - [외판원 문제 / TSP] 크리스토피데스 알고리즘 (Christofides' Algorithm)

[외판원 문제 / TSP] 크리스토피데스 알고리즘 (Christofides' Algorithm)

이번 포스트에서는 path TSP가 어떤 문제인지 알아보고, 동시에 이 문제를 크리스토피데스 알고리즘을 활용하여 풀어보도록 하겠습니다. 메트릭(metric)과 크리스토피데스 알고리즘에 대해서 잘 알고 있다는 가정 아래 본문이 작성되었습니다. 만약 이것들에 대해서 잘 모르신다면 이전 포스트를 읽어 주시기 바랍니다. 특히, 크리스토피데스 알고리즘의 분석 방법은 이전 포스트를 많이 차용하니 참고 바랍니다.

문제 정의

Photo by Rocco Dipoppa on Unsplash

TSP는 어떤 지점들이 주어졌을 때, 한 지점에서 출발하여 모든 지점을 정확히 한 번씩만 거쳐서 출발 지점으로 다시 돌아오는 방법 중 가장 거리가 짧은 것이 무엇인지 찾는 문제였습니다. 이전 포스트에서 다음과 같은 상황을 예시로 들었습니다. 여러분이 전국구의 유명 밴드의 순회 공연을 기획하는 사람이라고 해보죠. 어떤 도시에서 콘서트를 열지는 이미 정했지만, 어떤 순서대로 콘서트를 열지는 아직 정해지지 않았습니다. 여러 요인이 있겠지만, 아무래도 밴드 구성원들의 피로도나 여행 경비를 생각했을 때 가장 거리가 짧은 순회 경로를 짜는 것이 바람직할 것입니다. 딱 이 상황이 TSP로 볼 수 있었습니다.

 

그냥 TSP를 해결하면 얻는 답은 어떤 순환(cycle)입니다. 즉, 한 지점에서 출발하여 다시 그 지점으로 돌아오는 것이죠. 근데 위 예시에 대입하여 생각해보면 이는 약간 불필요한 비용이 포함되어 있습니다. 만약 서울에서 출발했다고 가정했다면, TSP를 통해 얻는 답은 다시 서울로 돌아오는 비용도 들어있는 것입니다. 그냥 모든 지점을 한 번씩만 방문하면 된다면 굳이 그 비용을 낼 필요는 없겠죠. 따라서 우리는 다음과 같은 문제를 생각해 볼 수 있습니다.

경로 외판원 문제(Path traveling salesman problem)

---

어떤 지점의 집합 \(V\)와 그것들의 거리를 이루는 metric \(d\)가 주어졌을 때, 모든 지점을 정확히 한 번씩만 방문하는 경로(path) 중 가장 거리가 짧은 것을 구하시오.

일단 이 문제도 NP-난해(NP-hard)합니다. 어떤 그래프가 주어졌을 때 해밀턴 순환(Hamiltonian cycle)을 찾는 것이 NP-완전(NP-complete)이어서 TSP가 NP-난해하였듯이, 어떤 그래프에서 모든 정점을 정확히 한 번씩만 방문하는 해밀턴 경로(Hamiltonian path)를 찾는 것도 NP-완전하기 때문에 path TSP도 NP-난해합니다. 따라서 이 문제도 근사적으로 해결하는 방법을 생각해 봐야합니다.

 

자연스럽게 이 문제는 다음과 같이 세 가지의 변형을 생각해 볼 수 있습니다.

1. 경로의 출발 지점과 도착 지점이 정해지지 않은 경우
2. 경로의 출발 지점은 \(s\)로 정해졌으나 도착 지점은 정해지지 않은 경우(혹은, 반대로 도착 지점만 정해진 경우)
3. 경로의 출발 지점은 \(s\)로, 도착 지점은 \(t\)로 정해진 경우(단, \(s \neq t\))

모두 비슷해 보이지만 약간씩 다릅니다. 사실은 1번 문제보다는 2번 문제가, 그리고 2번 문제보다는 3번 문제가 어렵습니다. 왜냐하면 뒤 문제를 푸는 근사 알고리즘이 존재한다면 앞 문제를 동일한 근사비로 해결하는 알고리즘이 존재하기 때문입니다. 예를 들어 2번 문제를 \(\rho\)의 근사비로 해결하는 근사 알고리즘 \(\mathcal{A}\)가 있다고 해보죠. 그러면 모든 지점 \(v \in V\)에 대해서, \(v\)를 \(s\)로 두고 \(\mathcal{A}\)를 수행합니다. 그렇게 얻은 여러 경로 중에서 가장 거리가 짧은 것을 출력하면 그것은 출발 지점과 도착 지점이 정해지지 않은 상태에서 모든 지점을 정확히 한 번씩만 방문하는 최단 경로에 비해 \(\rho\) 배 이내의 거리를 이루는 경로가 됩니다. 이는 1번 문제를 해결하는 \(\rho\)-근사 알고리즘이 됩니다.(증명은 어렵지 않으니 직접 해보세요!)

 

그렇다면 path TSP는 그냥 TSP에 비해서 난이도가 어떻게 될까요? 1번 문제와 2번 문제에 대해서는 잘 모르겠지만, 출발 지점과 도착 지점이 전부 정해지는 3번 문제는 TSP보다 쉽지 않다는 것을 보일 수 있습니다. 왜냐하면 3번 문제를 해결하는 \(\rho\)-근사 알고리즘 \(\mathcal{B}\)가 존재하면 TSP를 동일한 근사비로 다항 시간에 해결할 수 있기 때문입니다. 방법은 모든 지점 쌍 \((u, v) \in V \)에 대해서 \(s := u\), \(t := v\)로 하고 \(\mathcal{B}\)를 돌린 후 나온 경로에 \((u, v)\)를 덧댄 순환 중에서 가장 거리가 짧은 것은 반환하는 것입니다.(이것도 증명은 생략하죠. 직접 도전해 보세요!)

 

지금까지 여러 버전의 path TSP의 난이도에 대해서 알아보았습니다. 그러면 위 세 문제는 각각 어떤 근사비를 가질까요? 놀랍게도, 2번 문제는(그리고 자연스럽게 1번 문제도) 크리스토피데스 알고리즘을 활용하면 그냥 TSP와 동일한 근사비인 \(\frac{3}{2}\)의 근사비를 얻을 수 있습니다. 하지만 어려운 3번 문제는 어떨까요? 안타깝게도 크리스토피데스 알고리즘을 활용하면 \( \frac{5}{3} \)의 근사비를 얻게 됩니다. 심지어 크리스토피데스 알고리즘만 가지고는 \( \frac{5}{3} \)보다 좋은 근사비를 얻을 수 없다는 것도 보일 수 있습니다.^[2] 아래에서 하나씩 차근히 이에 대해 알아보도록 하죠.

출발 지점만 정해진 경우

우리가 알고있는 크리스토피데스 알고리즘은 TSP를 해결하는 근사 알고리즘이므로 출발 지점이 정해진 path TSP를 해결하기 위해서는 이 알고리즘을 약간 수정할 필요가 있습니다. 바로 알고리즘이 어떻게 수정되는지 보기 전에 먼저 그림 예시를 통해 직관적으로 알아보도록 하겠습니다.

직관적으로 이해하기

시작은 크리스토피데스 알고리즘과 동일합니다. 바로 지점 \(V\)를 모두 연결하면서 \(d\)에 가장 짧은 minimum-cost spanning tree \(T\)를 찾는 것입니다.

그림 1. MST \(T\) 예시. \(s\)는 사각형으로 칠했음

본래의 크리스토피데스 알고리즘이라면 다음 단계에서 홀수의 차수를 갖는 지점을 찾았습니다. 그 이유는 홀수의 차수를 갖는 지점들만 가지고 minimum-cost perfect matching \(J\)를 만들어 이를 \(T\)에 덧대기 위함이었죠. 그러면 모든 지점이 \(T + J\) 위에서 짝수의 차수를 가지므로 오일러 회로(Eulerian circuit)이 존재하고, 이를 shortcut하면 원하는 해밀턴 순환을 얻을 수 있었습니다.

 

하지만 현재의 목표는 해밀턴 순환이 아닌 해밀턴 경로입니다. 해밀턴 순환을 구하기 위해 오일러 회로를 가지고 왔으니, 해밀턴 경로를 구하기 위해서는 무엇을 가지고 오면 될까요? 네, 바로 오일러 경로(Eulerian trail)입니다. 그것의 필요충분조건은 정확히 두 개의 정점이 홀수의 차수를 갖는 것이죠. 또한 홀수 차수의 정점이 각각 오일러 경로의 시작과 끝이 됩니다. 우리는 \(s\)가 반드시 출발 지점이 되어야 하므로 \(s\)의 차수는 이제 홀수가 되어야 합니다. 근데 여기서 만약 \(s\)가 \(T\) 위에서 짝수 차수를 갖는다면, matching에 참여를 시켜서 차수를 바꿔줘야 되겠죠.

그림 2. \(T\)에서 잘못된 차수를 갖는 정점들. \(s\)는 시작점이므로 홀수의 차수를 가저야 한다.

문제는 그렇게 되면 잘못된 차수를 갖는 정점의 개수가 홀수가 된다는 것입니다. 앞서 임의의 그래프에서 홀수의 차수를 갖는 정점의 개수는 악수 정리(handshake lemma)에 의해 정확히 짝수 개라는 것을 증명하였습니다. 근데 만약 \(s\)가 홀수의 차수를 갖고 있었다면 이는 잘못된 차수를 가진 것이 아닙니다. 반대로 만약 \(s\)가 짝수의 차수를 갖고 있었다면 이는 잘못된 차수를 갖는 것이죠. 따라서 잘못된 차수를 갖는 정점의 개수는 홀수의 차수를 갖는 정점의 개수와 정확히 1의 차이를 갖게 됩니다. 그러니 잘못된 차수를 갖는 정점으로만 이루어진 perfect matching을 만들 수 없게 됩니다.

 

무언가 이상하다고 느끼셨을 것입니다. 그렇다면 잘 이해하신 것입니다. 제가 계속 잘못된 차수의 개수가 홀수 개라고 말했는데, 사실 이들 중에서 하나는 우리가 들어내고 생각할 수 있습니다. 왜냐하면, 오일러 경로가 존재하기 위해서는 정확히 두 개의 정점이 홀수의 차수를 가져야 하기 때문입니다. 하나는 \(s\)로 정해졌지만, 나머지 하나는 아직 정해지지 않았습니다. 따라서 위에서 잘못된 차수의 정점을 하나씩 생략한 나머지 정점들에 대한 minimum-cost perfect matching을 구한 후에 그중 가장 거리가 짧은 것을 가지고 오겠습니다. 이를 \(J\)라고 부르겠습니다.

 

이제 항상 그렇듯이 \(T + J \)를 고려합니다.(여기서 \(+\)는 간선의 중복을 허용하여 넣는 작업입니다.) 우리의 목표는 이 위에서 오일러 경로를 찾는 것입니다. 먼저 \(s\)가 원래 \(T\)에서부터 홀수 차수를 갖거나 \(s\)가 \(J\)에 참여하는 경우를 생각해 보겠습니다. 그러면 \(s\)와 함께 \(J\)에 참여하지 않는 잘못된 차수의 지점만이 \(T + J\) 위에서 홀수의 차수를 갖게 됩니다. 여기서 후자의 지점을 \(t\)라고 부르겠습니다.

그림 3. \(J\)가 \(s\)에 참여하는 예시. 정확히 \(s\)와 \(t := h\)만 \(T + J\) 위에서 홀수의 차수를 갖는다.

그러면 \(T + J\) 위에는 반드시 \(s\)에서 \(t\)로 모든 간선을 경유하여 도착하는 오일러 경로가 존재하며, 이를 다항 시간에 찾을 수 있습니다. 이 경로를 shortcut하면 우리가 원하는 결과가 됩니다.

 

남은 경우는 \(s\)가 \(T\)에서 짝수의 차수를 가졌는데 \(s\)가 \(J\)에서 빠진 상황입니다. 이는 처음에 의도한 상황이 아닙니다. 처음에 \(s\)의 차수가 짝수여서 이를 \(J\)에 포함시켜 수정하려고 했는데, 다시 빠져버려서 말짱 도루묵이 된 것이죠. 하지만 이 경우는 다르게 생각하면 \(J\)에 참여하는 지점이 원래 \(T\)에서 홀수의 차수를 갖는 지점 전부를 의미한다는 것을 알려줍니다. 즉, \(T + J\) 위에서 모든 지점의 차수는 짝수가 됩니다.

그림 4. \(s\)가 \(T\)에서 짝수의 차수를 가지나 \(J\)에는 참여하지 않는 예시. 모든 지점은 \(T + J\) 위에서 짝수의 차수를 갖는다.

이때는 그냥 \(T + J\)에서 \(s\)에 부속된 아무 간선 하나를 지워버리면 됩니다. 그 간선의 반대편을 \(t\)라고 하겠습니다. 그러면 정확히 \(s\)와 \(t\)가 홀수의 차수를 갖게 됩니다. 그러면 \(T + J - (s, t)\) 위에는 같은 이유로 \(s\)에서 \(t\)로 가는 오일러 경로가 존재하고, 이를 shortcut하면 원하는 결과를 얻게 됩니다.

그림 5. 그림 4에서 \( (s, a) \)를 지운 예시. 정확히 \(s\)와 \(t := a\)만 홀수의 차수를 갖는다.

알고리즘

이를 정리하면 다음과 같은 알고리즘을 얻게 됩니다.

Christofides-like algorithm for the path TSP with a pre-specified source

---

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

출력: \(s\)에서 출발하여 모든 지점을 정확히 한 번씩만 방문하는 경로

 

1. \(V\)를 정점으로 하고 간선의 cost가 \(d\)인 complete graph에 대해 minimum spanning tree \(T\)를 구한다.
2. \(T\) 위에서 \(s\)가 아닌데 홀수의 차수를 갖거나 \(s\)인데 짝수의 차수를 갖는 정점의 집합 \(S \subseteq V\)에 대해, \(S\)에서 하나의 정점만 참여하지 않는 minimum-cost matching \(J\)를 구한다.
3. \(T + J\) 위의 오일러 경로 \(P\)를 구한다. 만약 \(s \in S\)이고 \(s \notin V(J)\)이면 \(s\)에 부속된(incident) 임의의 간선 하나를 삭제한 후 \(P\)를 구한다.
4. \(s\)에서 출발하여 \(P\)를 따라 정점을 하나씩 방문하며 만약 이미 방문한 정점이면 shortcut한다.

분석

증명은 이전 포스트에서 소개해 드린 것과 비슷합니다. \(s\)에서 출발하여 모든 지점을 정확히 한 번씩만 방문하는 경로 중 가장 거리가 짧은 것을 \(P^\star\)라고 하겠습니다.

그림 6. \(P^\star\) 예시.

우리가 보일 것은 \( d(T + J) \leq \frac{3}{2} d(P^\star) \)입니다. 여기서 \(P^\star\)는 그 자체로 이미 spanning tree이기 때문에 \( d(T) \leq d(P^\star) \)임을 알 수 있습니다. 따라서 \( d(J) \leq \frac{1}{2} d(P^\star) \)를 구하면 증명은 완료됩니다. 여기서 \(J\)는 \(S\)에 대해 정확히 하나의 정점이 참여하지 않는 minimum-cost matching입니다. 따라서 이전 포스트에서 한 것과 똑같이 \[ d(J_1) + d(J_2) \leq d(P^\star) \tag{1} \]를 만족하는 \(S\)에서 정확히 하나의 정점만 참여하지 않는 어떤 matching \(J_1\)과 \(J_2\)를 만들 수 있다면 증명이 완료됩니다.

 

그것들을 만드는 과정도 이전과 비슷합니다. \(S\)를 기준으로 \(P^\star\)를 잘 끊어주는 것이죠. 좀더 상세히 말씀을 드리자면, 먼저 \(S\)를 \(s\)에서 출발하여 \(P^\star\)에 나타난 순서대로 이름을 붙여주도록 하겠습니다. 앞에서 \(S\)는 정확히 홀수 개의 정점을 가진다는 것을 보였으므로 \[ S := \{ 1, 2, \cdots, 2m + 1 \} \]으로 표현할 수 있습니다. 그러면 \[ \begin{array}{lr} J_1 & := \{ (1, 2), (3, 4), \cdots, (2m - 1, 2m) \} \\ J_2 & := \{ (2, 3), (4, 5), \cdots, (2m, 2m+1) \} \end{array}\]이 우리가 원하는 것이 됩니다.

그림 7. \(J_1\)과 \(J_2\) 만드는 예시. 빨간 정점은 \(S\)에 속한 정점을 의미한다. \(s\)에서 출발하여 \(P^\star\)에 나타난 순서대로 \(S\)의 이름을 붙이면 \(1 := s\), \(2 := a\), \(3 := g\), \(4 := e\), \(5 := h\), \(6 := d\), \(7 := b\)가 된다. 따라서 \(J_1 := \{(s, a), (g, e), (h, d)\}\), \(J_2 := \{ (a, g), (e, h), (d, b) \}\)가 된다.

먼저 \(J_1\)은 \(S\)에서 \(2m + 1\)만 참여하지 않는 matching이고, \(J_2\)는 \(1\)만 참여하지 않는 matching이므로 해당 조건을 만족한다는 것을 알 수 있습니다. 또한 이전 포스트에서 본 것과 비슷하게 \(P^\star\)를 쪼개서 \(J_1\), \(J_2\)를 이끌어낼 수 있습니다.(그림 7을 참고하세요.) 따라서 이 알고리즘은 출발 지점만 정해진 path TSP를 1.5의 근사비로 해결하는 알고리즘이 됩니다.

출발 지점과 도착 지점이 모두 정해진 경우

위 절에서 출발 지점만 정해지는 경우에는 크리스토피데스 알고리즘을 약간 수정하면 1.5의 근사비를 갖는다는 것을 알아보았습니다. 과연 출발 지점 \(s\)와 도착 지점 \(t\)가 모두 정해진 경우에는 어떻게 될까요? 먼저 크리스토피데스 알고리즘을 이 버전에 맞게 수정해 보겠습니다. 위와 비슷한데, 약간의 차이점이라면 이번에는 반드시 \(s\)에서 출발해서 \(t\)로 끝나야 한다는 것입니다. 따라서 minimum spanning tree \(T\)에서 \(s\)와 \(t\)가 짝수의 차수를 갖는다면 우리는 이를 수정해 주어야 하며, 반대로 나머지 지점들은 홀수의 차수를 가지게 되었을 때 수정해 주어야 합니다. 흥미로운 점은 이 경우에는 \(T\)에 잘못된 차수를 갖는 지점의 개수가 정확히 짝수 개가 된다는 것입니다.(\(s\)와 \(t\)가 갖는 차수를 경우의 수로 나누어서 생각하면 쉽게 보일 수 있습니다.) 따라서 잘못된 차수를 갖는 지점만으로 perfect matching을 만들 수 있게 됩니다. 이후의 과정은 동일합니다. 이를 정리하면 다음과 같습니다.

Christofides-like algorithm for the \(s\)-\(t\) path TSP

---

입력: 지점 \(V\), metric \(d: V \times V \rightarrow \mathbb{Q}_+\), 출발 지점 \(s \in V\), 도착 지점 \(t \in V\) (단, \(s \neq t\))

출력: \(s\)에서 출발하여 모든 정점을 한 번씩 지나 \(t\)에 도착하는 경로

 

1. \(V\)를 정점으로 하고 간선의 cost가 \(d\)인 complete graph에 대해 minimum spanning tree \(T\)를 구한다.
2. \(T\) 위에서 \(s\)나 \(t\)가 아닌데 홀수의 차수를 갖거나 \(s\)나 \(t\)인데 짝수의 차수를 갖는 정점의 집합을 \(S \subseteq V \)에 대해 \(S\)의 모든 정점이 참여하는 minimum-cost perfect matching \(J\)를 구한다.
3. \(T + J\) 위에서 \(s\)에서 출발하여 \(t\)에 도착하는 오일러 경로 \(P\)를 찾는다.
4. \(s\)에서 출발하여 \(P\)를 따라 정점을 하나씩 방문하며 이미 방문한 정점이면 shortcut한다.

나쁜 출력을 주는 예시

안타깝게도 이 알고리즘은 1.5의 근사비를 갖지 못합니다. 다음과 같은 예시를 생각해 보겠습니다.

그림 8. 입력의 예시.

그림 8과 같은 가중치가 있는 그래프 위에서 입력을 정의하겠습니다. \(V\)는 이 그래프의 정점과 동일하며 \(s\)와 \(t\)도 그림의 하단에 주어진 대로입니다. 임의의 두 정점 \(u, v \in V \)에 대해 \(d(u,v)\)는 \(u\)에서 \(v\)로 가는 최단 경로의 길이로 정하겠습니다. 예를 들어, \(d(c, e) = 200\), \(d(b, f) = 102\)가 됩니다. 따로 보이지는 않겠습니다만, 이렇게 얻은 \(d\)도 metric의 조건을 모두 만족합니다.

 

알고리즘의 단계 1과 2에서 다음 그림과 같이 \(T\)와 \(J\)를 찾았다고 해보겠습니다.

그림 9. MST \(T\)와 그에 따른 \(S\), \(J\)의 예시. 검정색 실선은 \(T\), 빨간 정점은 그에 따른 \(S\), 마지막으로 초록색 파선은 \(J\)를 나타낸 것이다.

이 위에서 오일러 경로를 찾고 shortcut을 하면 다음과 같은 해밀턴 경로를 얻습니다.

그림 10. 그림 9를 shortcut하여 얻은 해밀턴 경로.

이 해밀턴 경로의 거리를 구하면 총 \(506\)이 됩니다.

그림 11. 그림 8의 최적해 예시

그에 반해 이 입력에는 위 그림과 같이 \(306\)의 거리값을 갖는 최적해를 가지며, 이때 두 거리의 비를 구하면 \( \frac{506}{306} \approx \frac{5}{3} \)이 됩니다. 이를 통해 우리는 위 알고리즘이 \( \frac{5}{3} \)보다는 좋은 근사비를 가질 수 없다는 것을 추론할 수 있습니다.

분석

다행히도 이 알고리즘은 위에서 구한 것과 동일한 \( \frac{5}{3} \)의 근사비를 갖는다는 것을 증명할 수 있습니다. 다만 그 분석은 위에서 사용한 것과 유사해 보이면서도 상당 부분 다릅니다. 먼저 \(s\)에서 \(t\)까지 모든 지점을 정확히 한 번씩만 방문하는 경로 중 가장 거리가 짧은 것을 \(P^\star\)라고 부르겠습니다. 앞에서와 유사한 점은 \[ d(J) \leq \frac{2}{3} d(P^\star) \tag{2} \]를 보임으로써 \( d(T + J) \leq \frac{5}{3} d(P^\star) \)를 증명한다는 것입니다.

그림 12. \(P^\star\)의 예시.

다른 점은 당연히 식 2를 보이는 방법입니다. 앞에서는 분모에 2가 들어가서 matching을 두 개 가지고 왔습니다. 하지만 이번에는 분모에 3이 들어가므로 matching이 세 개가 필요할 것으로 보입니다. 대신 분자에 2가 들어갔으므로 아마도 \(P^\star\)를 두 번 겹치거나, \(P^\star\) 하나에 상응하는 무언가를 \(P^\star\)와 함께 쓸 수 있을 것입니다.

그림 13. \(T\)의 예시. 빨간 정점은 잘못된 차수를 갖는 정점의 집합 \(S\)를 표현한 것이다.

이 아이디어를 정형화 시켜보도록 하겠습니다. 먼저 알고리즘에서 구한 minimum spanning tree \(T\)를 가지고 옵니다. 잘 아시다시피 \(P^\star\)는 그 자체로 spanning tree이기 때문에 \(d(T) \leq d(P^\star)\)입니다. 즉, \(T\)를 \(P^\star\)에 상응하는 무언가로 쓸 수 있습니다.

그림 14. \( P^\star + T \)의 예시. 보라색 실선은 \(P^\star\)에서 검정색 파선은 \(T\)로부터 왔다. \(S\)의 정점은 모두 홀수의 차수를 갖고 나머지 정점은 모두 짝수의 차수를 갖는다는 것도 확인할 수 있다.

따라서 만약에 우리가 \(P^\star + T\) 위에서 \(S\)로 이루어진 perfect matching을 세 개 찾고, 각각을 \(J_1\), \(J_2\), \(J_3\)라고 했을 때 \[ d(J_1) + d(J_2) + d(J_3) \leq d(P^\star + T) \leq 2d(P^\star) \tag{3} \]가 만족하게 만든다면, 식 2를 증명할 수 있게 됩니다. 왜냐하면 \[ d(J) \leq \min\{ d(J_1), d(J_2), d(J_3) \} \leq \frac{2}{3} d(P^\star) \]가 되기 때문이죠.

 

들어가기 앞서, \(P^\star + T\)가 갖는 한 가지 재미있는 성질을 소개하겠습니다. 바로 이 위에서는 \(S\)의 정점은 모두 홀수의 차수를 갖고, 그 외의 정점은 모두 짝수의 차수를 갖는다는 점입니다. 증명은 간단합니다. \(T\)에서 \(S\)는 \(s\)나 \(t\)이면 짝수, 그외의 경우에는 홀수의 차수를 가졌습니다. 반면 \(P^\star\)에서는 \(s\)와 \(t\)는 1의 차수를, 그외의 경우는 2의 차수를 갖습니다. 즉, \(s\)와 \(t\)의 차수의 홀짝성만 뒤바뀌게 됩니다. 따라서 \(P^\star + T\)에서 \(S\)만 홀수의 차수를 갖게 되는 것이죠.

 

이제 본론으로 들어오도록 하겠습니다. 첫 번째로 \(J_1\)은 \(P^\star + T\) 위에서 \(P^\star\)를 따라가면서 만듭니다. 간단히 표현하기 위하여 \(S\)를 \(s\)에서 출발하여 \(P^\star\)를 따라가며 나타난 순서대로 이름을 붙여주도록 하겠습니다. \(S\)의 크기가 항상 짝수라는 점을 알고 있으므로 \[ S := \{1, 2, \cdots, 2m \} \]으로 표현하겠습니다. 예를 들어, 그림 14에서는 \(1 := s\), \(2 := a\), \(3 := d\), \(4 := b\), \(5 := h\), \(6 := e\)가 되겠죠.

그림 15. \(E_1\)의 예시.

여기서 \(E_1 \subseteq E(P^\star)\)를 다음과 같이 만듭니다. 먼저 \(1\)에서 출발하여 \(P^\star\)를 따라 \(2\)가 나올 때까지 모두 \(E_1\)에 집어넣습니다. 다음에는 \(3\)에서 출발하여 \(P^\star\)를 따라 \(4\)에 도달할 때까지 집어넣습니다. 이를 \(S\)가 끝날 때까지 반복합니다. 그러면 \(E_1\)은 분명히 \(1\)과 \(2\), \(3\)과 \(4\)처럼 임의의 \(k = 1, \cdots, m\)에 대해 \(2k - 1\)과 \(2k\)를 잇는 경로(path)들의 집합으로 표현될 것입니다.

그림 16. \(J_1\)의 예시. 그림 15에서 \( \langle h, f, e \rangle \)가 \((h, e)\)로 shortcut됨을 확인할 수 있다.

거리 \(d\)가 metric이므로 그것들의 끝점을 곧장 연결한다고 그 거리가 늘어나지 않습니다. 따라서 \[J_1 := \{ (1, 2),  (3, 4), \cdots, (2m - 1, 2m) \}\]으로 정의하면 우리는 \[ d(J_1) = \sum_{k = 1}^m d(2k-1, 2k) \leq \sum_{e \in E_1} d(e) = d(E_1) \tag{4} \]이라는 사실을 이끌어낼 수 있습니다.

 

나머지 \(J_2\)와 \(J_3\)는 \(E_1\)이 아닌 간선에서 이끌어 내야 식 3을 유도할 수 있을 것입니다. 따라서 이제부터는 \(P^\star + T - E_1\)을 고려해 보도록 하겠습니다.

그림 17. \(P^\star + T - E_1\)의 예시.

여기서 \(P^\star + T - E_1\)은 흥미로운 성질을 갖습니다. 앞에서 우리는 \(P^\star + T\) 위에서는 \(S\)의 정점만 홀수 차수를 갖고 나머지 정점은 짝수 차수를 갖는다고 하였습니다. 그런데 \(E_1\)은 정확히 \(S\)의 정점만 1의 차수를 갖고, 나머지 정점은 2(아니면 0)의 차수를 갖습니다. 따라서 \(S\)의 차수의 홀짝성만 뒤바꿔주는 결과를 갖게 되어 \(P^\star + T - E_1\)의 모든 정점은 짝수 차수를 갖습니다.

그림 18. 그림 17을 shortcut하여 얻은 해밀턴 순환 \(H\).

그러므로 \(P^\star + T - E_1\)에는 오일러 회로가 존재하고 이를 shortcut하면 \[ d(H) \leq d(P^\star + T - E_1) \tag{5} \]을 만족하는 해밀턴 순환 \(H\)를 얻을 수 있습니다. 

그림 19. 그림 18에서 \(J_2\)와 \(J_3\)를 얻은 예시.

우리는 이미 이전 포스트에서 어떤 해밀턴 순환 \(H\)이 주어졌을 때 두 matching의 거리의 합이 \(d(H)\)보다 작거나 같은 \(S\)의 perfect matching 두 개를 구하는 방법을 배웠습니다. 이를 적용하면, \[ d(J_2) + d(J_3) \leq d(H) \tag{6} \]인 \(S\)의 perfect matching \(J_2\)와 \(J_3\)를 구할 수 있게 됩니다.

 

위에서 얻은 식 4-6을 정리하면 식 3을 유도할 수 있으며, 이것으로 모든 증명이 마무리됩니다.

마치며

이번 글에서는 path TSP가 무엇이고 이를 근사적으로 해결하는 방법에 대해서 공부했습니다. 특히 본문에서 소개한 근사 알고리즘은 모두 크리스토피데스 알고리즘을 약간씩 변형하여 적용한 것이었습니다. Path TSP는 크게 세 가지의 버전으로 생각할 수 있습니다. 하나는 출발 지점과 도착 지점이 정해지지 않은 경우, 다른 하나는 출발 지점만(혹은 도착 지점만) 정해진 경우, 마지막으로는 출발 지점과 도착 지점이 모두 정해진 경우입니다. 이때 출발 지점이나 도착 지점이 최대 하나만 정해진 경우에는 기존의 TSP에서 얻은 것과 동일한 1.5의 근사비를 얻을 수 있었습니다. 하지만 출발 지점과 도착 지점이 모두 정해진 경우에는 \(\frac{5}{3} \approx 1.667\)의 근사비를 가지게 되었습니다. 게다가 이 방법으로는 아무래도 더 좋은 근사비를 얻기 힘들겠다는 예시도 함께 확인했죠.

 

과연 출발 지점과 도착 지점이 모두 정해진 버전, 소위 \(s\)-\(t\) path TSP를 보다 좋은 근사비로 해결하는 방법이 존재할까요? 이는 \( \frac{5}{3} \)의 근사비가 밝혀진 이래로 수십년간 미해결 상태로 남아있었습니다만, An, Kleinberg, & Shmoys의 \( \frac{1 + \sqrt 5}{2} \approx 1.619 \)-근사 알고리즘^[1]을 필두로 많은 연구가 이루어 졌으며 결국 최근 Zenklusen에 의해 다른 문제들과 동일한 1.5의 근사비를 갖는 알고리즘^[3]이 존재한다는 것이 밝혀졌습니다.

 

다시 말해, 현재로서는 TSP와 \(s\)-\(t\) path TSP의 근사비가 동일한 상태입니다. 서두에 \(s\)-\(t\) path TSP를 해결하는 \(\rho\)-근사 알고리즘이 있으면 TSP를 \(\rho\)의 근사비로 해결하는 방법이 있다고 알려드렸습니다. 따라서 \(s\)-\(t\) path TSP에서 1.5보다 좋은 근사비를 갖는 알고리즘을 만든다면, 40년동안 해결되지 못한 문제인 TSP를 1.5보다 좋은 근사비로 다항 시간에 해결할 수 있는지를 풀게 될 것입니다. 과연 정답은 무엇일까요?

 

모쪼록 읽어 주셔서 고맙습니다.

참조 문헌

[1] Hyung-Chan An, Robert Kleinberg, and David B. Shmoys. Improving christofides' algorithm for the \(s\)-\(t\) path TSP. Journal of the ACM, 62(5):1-28, 2015.

 

[2] J. A. Hoogeveen. Analysis of Christofides' heuristic: Some paths are more difficult than cycles. Operations Research Letters, 10(5):291-295, 1991.

 

[3] Rico Zenklusen. A 1.5-approximation for path TSP. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp.1539-1549, 2019.