Traveling Sales Person Problem (TSP Problem)
방문 판매원 문제
[Input]
Positive Weighted Undirected Graph \(G = (V, E)\)
Positive Real Number \(k\)
[Query]
Ver. Desicion Problem : \(G\)에 길이가 \(k\) 이하인 해밀토니안 사이클*이 존재하는가?
Ver. Optimization Problem : \(G\)에서 길이가 가장 짧은 해밀토니안 사이클의 길이는 얼마인가?
* Hamiltonian Cycle (해밀토니안 사이클; 한 붓 그리기) (URL)
- 그래프의 모든 정점을 한 번씩만 방문하여 원래의 출발점으로 되돌아오는 경로를 의미한다.
- 특히, Complete Graph(완전 그래프; 모든 정점 사이에 간선이 존재하는 그래프)에서는
해밀토니안 사이클이 무조건 존재하며, 총 \((n-1)!\)개의 해밀토니안 사이클이 존재한다.
- TSP 문제는 이 \((n-1)!\)개의 해밀토니안 사이클 중, 가장 짧은 것을 찾아내는 문제이다.
Mechanism (원리)
- TSP는 NP-Hard에 속하는 문제로, 다항식 시간에 최적해를 도출해낼 수 없다.
- 그러므로, 근사 알고리즘을 통해 제한된 시간에 최대한 최적해에 가까운 해(근사해)를 도출하는 것을 목표로 한다.
- 단, 아래 근사법들은 주어진 그래프 \(G = (V, E)\)의 정점 \(v \in V\)들이
The Triangle Inequality (삼각 부등식) (URL)을 만족한다는 가정 하에 수행할 수 있으며,
삼각 부등식을 만족시키지 못하는 경우, "근사해의 값이 최적해의 값의 수백만 배 이하다."라는 보장조차 못한다.
(즉, 유의미한 근사해를 찾아내지 못한다. 이는 본 포스트 하단의 Verification (검증) Section에서 증명한다.)
- 삼각 부등식을 만족시키지 못하는 경우에서, TSP를 풀어야 하는 경우
현업에서는 2-Opt, 3-Opt, Lin-Kernighan 알고리즘 등 휴리스틱 알고리즘들과, 유전 알고리즘, 타부 서치 등
효율적인 공간 탐색 알고리즘 등을 동원하여 최적해에 근접한 해를 도출시킨다.
(하지만, 이들은 이론적으로 최적해 보장은 하지 못하나, 실제로는 좋은 성능을 보이고 있는 알고리즘들이다.)
Approxiamtion Type 1
TSP Optimization Problem의 Instance \(G = (V, E)\)가 주어졌을 때,
근사해를 구하는 절차는 아래와 같다.
| Phase | Description |
| (a) | - 주어진 그래프 \(G = (V, E)\) 이다. - 그래프 \(G\)는 완전 그래프이다. (즉, 모든 가능한 정점 Pair들에 대한 간선이 존재한다.) - 이 그림에서는 간결성을 위해, 간선들을 표현하지 않았다. - 각 간선들의 가중치는 각 정점들 사이의 직선 거리라 하자. |
| (b) | - Minimum Spanning Tree Algorithm을 통해, \(G\)의 Minimum Spanning Tree를 구한다. - 이 Tree를 따라 DFS를 수행하면서 정점들을 방문하며 시작 정점으로 되돌아온다. (시작 정점으로 되돌아와야 하기 때문에, 2번 이상 방문하는 정점들도 생긴다.) |
| (c) | - Phase (b)의 순서에서 같은 정점을 2번 이상 방문해야 할 경우에 맞닥뜨리면 방문하지 않은 정점으로 바로가는 지름길을 택하도록 한다. (그림에서 초록색 간선이 이러한 "지름길"에 해당된다.) |
| (d) | - 이러한 절차로 만들어진 Cycle을 근사해로서 리턴한다. - 그림 (c)와 그림 (d)의 그래프는 동치이다. (그냥 (c)에서의 그래프를 보기 좋게 풀어놓은 것일 뿐이다.) |
※ 이러한 방법으로 도출된 사이클의 길이는 최적해에서의 사이클의 길이의 2배를 넘지 않는다고 보장되는데,
이는 본 포스트 하단의 Verification (검증) Section에서 증명한다.)
Christofides Approximation Algorithm (크리스토피드 근사 알고리즘)
- 크리스토피드가 제안한, TSP Optimization Problem의 Instance \(G = (V, E)\)가 주어졌을 때,
근사해를 구하는 절차는 아래와 같다.
| Phase | Description |
| (a) | - 주어진 그래프 \(G = (V, E)\) 이다. - 그래프 \(G\)는 완전 그래프이다. (즉, 모든 가능한 정점 Pair들에 대한 간선이 존재한다.) - 이 그림에서는 간결성을 위해, 간선들을 표현하지 않았다. - 각 간선들의 가중치는 각 정점들 사이의 직선 거리라 하자. |
| (b) | - Minimum Spanning Tree Algorithm을 통해, \(G\)의 Minimum Spanning Tree를 구한다. - 이 Tree를 정점들 중, 차수가 홀수인 정점들을 추출한다. (그림에서는 회색으로 색칠된 정점들이 추출된 정점들이다.) - 어떤 그래프든, 차수가 홀수인 정점은 항상 짝수개로 존재한다. |
| (c) | - Phase (b)에서 추출한 정점들을 2개씩 짝지어 간선으로 연결하되, 간선 길이의 합이 최소가 되도록 짝을 짓는다. - 이를 최소 매칭이라 하며, 이 매칭에 관여하는 정점들의 개수가 \(m\)개라면, 최소 매칭은 \(O(m^3)\)의 시간이 소요된다. (최소 매칭을 통해 생성된 간선들을 그림에서는 검은색 파선으로 표현했다.) - 이 간선들까지 그래프 \(G\)에 추가하면 모든 정점의 차수가 짝수가 되어 Eulerian Graph(오일러 그래프)가 된다. - 오일러 그래프에는 모든 간선을 한 번씩 지나는 오일러 사이클이 존재하는데, 이러한 오일러 사이클을 하나 찾는다. (그림에서는 하나의 오일러 사이클을 초록색 파선으로 표현했다.) |
| (d) | - Phase (c)에서 만들어진 오일러 사이클에서 두 번 이상 방문하는 정점이 생길 경우, 지름길을 택해 해당하는 정점을 뛰어 넘어 두 번 이상 방문되는 정점이 생기지 않도록 한다. - 이렇게 만들어진 사이클을 근사해로서 리턴한다. |
※ 이러한 방법으로 도출된 사이클의 길이는 최적해에서의 사이클의 길이의 1.5배를 넘지 않는다고 보장되는데,
이는 본 포스트 하단의 Verification (검증) Section에서 증명한다.)
State Space Tree Search with Brute Force (주먹구구식 상태 공간 트리 탐색)
* State Space Tree Search (상태 공간 트리 탐색) (URL)
- 위와 같은, Directed Graph에서 Asymmetric TSP 문제를 계산할 때,
상태 공간 트리에서 사전순으로 모든 경우의 수를 계산한다 하면
상태 공간 트리는 아래 그림처럼 구성될 것이다.
- 이 경우, 1번 정점에서 시작하여, 모든 정점을 방문하고 되돌아오는 모든 경로의 경우의 수를 계산하게 된다.
- 즉, \(|V|!\)에 비례하는 시간이 소요될 것이다.
State Space Tree Search with Branch and Bound (분기 한정 방법을 통한 상태 공간 트리 탐색)
- 위와 같은, Directed Graph에서 Asymmetric TSP 문제를 계산할 때,
상태 공간 트리를 분기 한정법으로 탐색한다 하면
상태 공간 트리는 아래 그림처럼 구성될 것이다.
- 상태 공간 트리를 Brute Force로 탐색하는 것에 비해, Branch and Bound에서는
Promising하지 않은 부분은 Prunning(X 표시)하여 시간을 절약하는 부분이 눈에 띈다.
- 각 노드에 부여된 번호는 곧 탐색 순서를 의미한다.
노드 내부의 수열(a-b-c)은 부분 경로를 의미하고,
노드 옆 괄호 안의 수는 해당 경로로 진행하여 경로를 완성했을 때의 경로 길이의 하한값이며,
괄호 아래에 '+'기호로 표현된 식은 하한값이 계산된 근거가 되는 식이다.
- 각 Leaf의 아래 사각형 안의 수는 각각의 경우의 사이클의 길이이며,
그 위의 수열은 각각의 경우에 방문하는 정점의 순서이다.
- 탐색 초기의 하한값 33이 계산된 근거는 아래와 같다.
정점 1에서의 진출 간선들의 길이 중 최솟값 = 10
정점 2에서의 진출 간선들의 길이 중 최솟값 = 10
정점 3에서의 진출 간선들의 길이 중 최솟값 = 7
정점 4에서의 진출 간선들의 길이 중 최솟값 = 3
정점 5에서의 진출 간선들의 길이 중 최솟값 = 3
이들의 합 = 33
(해밀토니안 사이클의 간선의 개수는 \(|V|\)이므로, 각 정점들의 저렴한 진출 간선들을 모아 형성한 사이클을
하한값으로 보는것이다. 사실, 이렇게 모은 간선들이 사이클을 이룰 가능성은 낮다.
그러므로 굉장히 Rough한 하한값이다.)
- 각 노드에서 하한값이 계산된 근거는 아래와 같다. (예시로, 6번 노드를 보자)
6번 노드는 정점 1, 2, 3은 이미 방문한 상태이므로, 정점 4, 5를 방문해야 한다.
정점 3에서의 진출 간선들의 길이 중 최솟값 = 7
정점 4에서의 진출 간선들의 길이 중 최솟값 = 3
정점 5에서의 진출 간선들의 길이 중 최솟값 = 3
이들의 합 = 13
즉, 앞으로 사이클의 길이에 더해질 값의 하한선은 13으로 계산한다.
- 최초의 Prunning은 하나의 온전한 해를 구한 이후부터 시작된다.
(즉, 구해놓은 해가 하나도 없을 경우, Prunning할 근거가 부족하다.)
State Space Tree Search with A* Algorithm (A* 알고리즘을 통한 상태 공간 트리 탐색)
* A* Algorithm (A* 알고리즘) (URL)
- 위와 같은, Directed Graph에서 Asymmetric TSP 문제를 계산할 때,
상태 공간 트리를 A* 알고리즘으로 탐색한다 하면
상태 공간 트리는 아래 그림처럼 구성될 것이다.
- A* 알고리즘에서는 \(f(x) = g(x) + h(x)\) 값이 가장 작은 값을 가진 노드를 다음 방문할 노드로 선정한다.
\(g(x)\) : 임의의 부분 경로 \(x\)에서 지금까지 지나온 경로의 길이
\(h(x)\) : 잔여 경로의 휴리스틱 추정치
- 위 그림에서 4번 노드(부분 경로 "1-2-5")의 계산식을 예로 들면,
"(33) 20 + 13"은 \(f(x) = 33\), \(g(x) = 20\), \(h(x) = 13\)을 의미한다.
(1번 정점 - 2번 정점 - 5번 정점에 대한 경로의 길이는 20이므로, \(g(x)\)값이 20으로 설정된 것이며,
나머지 3번 정점, 4번 정점, 5번 정점에 대한 휴리스틱값은
해당 정점들의 진출 간선중 가중치가 가장 작은 값들의 합이므로
\(h(x)\)값이 7+3+3=13으로 설정된 것이다.)
- 탐색 초기의 하한값 33이 계산된 근거는 아래와 같다.
정점 1에서의 진출 간선들의 길이 중 최솟값 = 10
정점 2에서의 진출 간선들의 길이 중 최솟값 = 10
정점 3에서의 진출 간선들의 길이 중 최솟값 = 7
정점 4에서의 진출 간선들의 길이 중 최솟값 = 3
정점 5에서의 진출 간선들의 길이 중 최솟값 = 3
이들의 합 = 33
(해밀토니안 사이클의 간선의 개수는 \(|V|\)이므로, 각 정점들의 저렴한 진출 간선들을 모아 형성한 사이클을
하한값으로 보는것이다. 사실, 이렇게 모은 간선들이 사이클을 이룰 가능성은 낮다.
그러므로 굉장히 Rough한 하한값이다.)
※ Branch and Bound 방법에서와 달리, A* 알고리즘에서는 임의의 Leaf가 방문되는 순간 알고리즘이 종료된다.
- A* 알고리즘에서, "리프 노드의 사이클 길이가 계산되는 것"과, "리프 노드를 방문하는 것"은 다른 개념이다.
먼제 경로의 길이를 "계산"한 다음, 계산된 값이 가장 작은 노드를 "방문"한다.
(즉, 계산이 방문보다 선행된다.)
- 처음으로 방문된 Leaf Node를 \(w\)라 하고,
\(w\)를 제외한 나머지 Leaf Node들에 대해
"이미 경로 길이가 계산된 Leaf" 그룹과
"아직 경로 길이가 계산되지 않은 Leaf" 그룹으로 나누자.
1) 이미 경로 길이가 계산된 Leaf Nodes
- \(w\)가 이들보다 먼저 방문되었다는 것은 이들의 길이가 \(w\)의 길이보다 긴 것을 의미하므로,
이 그룹에 속한 Leaf들은 최적해가 될 가능성이 없다.
2) 아직 경로 길이가 계산되지 않은 Leaf Nodes
- 아직 계산될 기회를 갖지 못했다는 것은 이들의 Ancestor Node들이 Nonpromising하다는 것을 의미하고,
Nonpromising한 Node의 자식 노드들의 길이는 모두 최적해가 될 가능성이 없으므로,
이 그룹에 속한 Leaf들은 최적해가 될 가능성이 없다.
(추정치는 실제로 계산된 값보다 더 작을 수 밖에 없는데, 이 추정치가 현재 도출된 해보다 더 크기 때문이다.)
- 이러한 이유에서, A* 알고리즘에서는 많은 시간이 절약된다.
- 그러나, 이런 문제의 경우 방문되지 않은 노드의 개수가 Exponential하게 증가하여
유한한 크기의 메모리를 가진 컴퓨터에서 관리가 불가능해질 수 있는데,
이러한 상황에서 메모리 사용을 적절히 제한한 관리 기법이 현재 A* 알고리즘의 연구 주제 중 하나이다.
Implementation (구현)
Performance (성능)
Verification (검증)
Theorem. Approxiamtion Type 1에서 도출된 근사해의 사이클의 길이는 최적해의 사이클의 길이의 2배를 넘지 않는다.
pf) (최소 신장 트리의 간선의 가중치의 합) < (TSP의 최적해의 사이클 길이) 이다.
최적해는 해밀토니안 사이클이며, 이를 이루는 간선 중 하나를 제거하면 신장 트리가 되기 때문이다.
이러한 최소 신장 트리에서 DFS를 수행하면,
거쳐가는 간선들의 길이의 합은 최소 신장 트리의 길이의 정확히 2배이다.
(모든 간선들을 2번씩 거치기 때문이다.)
여기서, 한 번 방문한 간선을 다시 방문하게 될 경우, 한 번도 방문하지 않은 정점으로 향하는 지름길을 택하게 되므로,
이렇게 만들어진 Hamiltonian Cycle은 최적해의 사이클 길이의 2배를 넘지 않는다.
Theorem. Christofides Approximation Algorithm에서 도출된 근사해의 사이클의 길이는
최적해의 사이클의 길이의 1.5배를 넘지 않는다.
pf) 크리스토피드 알고리즘에서는 최소 신장 트리와 치소 매칭에 있는 간선 중 일부(또는 전부)를 사용하여 해밀토니안 사이클을 만든다.
최소 신장 트리의 간선들의 길이는 최적해보다 짧고,
최소 매칭으로 생겨난 간선들의 길이는 최적해의 반을 넘을 수 없다.
그러므로, 크리스토피드 근사 알고리즘을 통해 생겨난 해밀토니안 사이클은 최적해의 1.5배를 넘을 수 없다.
Theorem. The Triangle Inequality(삼각 부등식)을 만족하지 않는 TSP의 Instance의 경우,
\(P \neq NP\)라면 어떠한 상수 \(p\)에 대해서도 최적해의 \(\rho\)배를 넘지 않는 해를 보장하는
다항식 시간 근사 알고리즘은 존재하지 않는다.
pf) \(\rho\)배를 넘지 않는 해를 보장하는 다항식 시간 알고리즘 \(A\)가 존재한다 가정하자.
이미 NP-Complete 문제로 알려진 Hamiltonian Cycle Problem이 P에 속함을 보이자.
Hamiltonian Cycle Problem의 Instance \(G = (V, E)\)에 대해,
\(E\)에 원래 있던 간선의 가중치는 1로 설정하고,
Hamiltonian Cycle Problem을 TSP로 Reduction하느라 생긴 새로운 간선의 가중치는 모두 \(\rho |V|+1\)로 설정한다.
(이 과정은 모두 다항식 시간에 이루어질 수 있다.)
이렇게 TSP 문제로 Reduction하며 만든 새로운 그래프를 \(G' = (V, E')\) 라 하자.
Hamiltonian Cycle Problem에서
"\(G\)에 해밀토니안 사이클이 존재하는가?"에 해당되는 Query는
TSP Problem에서
"\(G'\)에 대해 알고리즘 \(A\)가 길이가 \(\rho |V|\) 이하의 해를 도출해낼 수 있는가?"에 해당되는 Query로
대치할 수 있는데, 그 근거는 아래와 같다.
\(G\)에 해밀토니안 사이클이 존재하면, \(G'\)의 최적해의 길이는 \(|V|\)이다.
(기존에 존재해있던 간선의 가중치가 모두 1이기 때문이다.)
알고리즘 \(A\)는 최적해의 \(\rho\)배를 넘지 않는 해를 보장하므로, \(\rho|V|\) 이하의 해를 도출하게 된다.
또한, 알고리즘 \(A\)가 \(G'\)에 대해 \(\rho|V|\) 이하의 해밀토니안 사이클을 도출했다면,
이 사이클은 원래 \(E\)에 존재해있던 간선들로만 구성되어 있어야 한다.
(원래 \(E\)에 없던 간선의 가중치는 모두 \(\rho|V|+1\)이므로, 이러한 간선이 하나만 포함되어도
사이클의 길이가 \(\rho|V|\)를 넘어버리기 때문이다.)
즉, 이 해밀토니안 사이클은 원래 그래프 \(G\)에 있던 사이클이다.
따라서, 이러한 다항식 알고리즘 \(A\)가 존재하면
NP-완비인 Hamiltonian Cycle Problem에 대해 다항식 시간에 답을 낼 수 있어
Hamiltonian Cycle Problem은 P에 속하게 된다.
이렇게 되면, 하나의 NP-완비 문제가 P에 속하게 되어, 다른 NP-완비 문제들도 모두 P에 속하게 된다.
(즉, NP \(\subseteq\) P이고, P \(\subseteq\) NP임은 자명하므로, P = NP가 된다.)
위와 같은 논리 흐름을 하나의 명제로 축약하면,
"다항식 알고리즘 A가 존재하면 P = NP이다."인데,
이 가정이 참이라면, Contraposition(대우 명제) 또한 참이어야 하므로,
"P \(\neq\) NP이면 다항식 알고리즘 \(A\)는 존재할 수 없다."
또한 참이어야 한다.
현재까지는, 학계에서 P \(\neq\) NP 일것으로 강력히 "추정"하고 있어,
이러한 다항식 알고리즘 \(A\)는 존재할 수 없다고 결론지어야할 것이다.
Theorem. Traveling Sales Person Problem은 NP-Hard이다.
(여기서, TSP Problem은 Decision Problem, Optimization Problem 둘 다 내포한다.)
pf) 본 포스트의 상단에 Hamiltonian Cycle Problem을 TSP Decision Problem으로 Reduction하는 과정이 설명되어 있다.
즉, TSP Decision Problem은 NP-완비이다.
그러므로, TSP Decision Problem \(\leq_{p}\) TSP Optimization Problem 임을 증명한다.
먼저, TSP 결정 문제에서의 그래프 \(G\)를 TSP 최적화 문제에 그대로 옮겨오자.
(즉, Reduction에 추가적인 시간이 소요되지 않는다. = 다항식 시간에 변환 가능하다.)
TSP 결정 문제의 Query는 TSP 최적화 문제가 해결되면 덩달아 해결된다.
즉, \(G\)에 대해 TSP 최적화 문제를 해결하여
Optimum으로서 해밀토니안 사이클의 길이 \(M\)을 얻었다고 하자.
\(M \leq k\) 이면 TSP 결정 문제의 답은 Yes이고,
\(M > k\) 이면 TSP 결정 문제의 답은 No이다.
즉, TSP 최적화 문제를 통해 TSP 결정 문제의 답을 얻어낼 수 있으므로,
TSP Decision Problem \(\leq_{p}\) TSP Optimization Problem 이다.
따라서, TSP Optimization Problem은 NP-Hard이다.
* NP-완비성 이론의 구조상, 결정 문제가 아닌 문제들은 NP에 속할 수 없다.
Reference: Introduction to Algorithms 3E (CLRS)
(Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein 저, MIT Press, 2018)
Reference: 쉽게 배우는 알고리즘
(문병로 저, 한빛아카데미, 2018)
