Algorithm design - TSP(Traveling Salesperson Problem)

---

오일러

오일러(Leonhard Euler, 1707 - 1783)는 일생동안 800편에 육박하는 논문을 냈다고 하는데 그만큼 다양한 주제에 화두를 던진 학자이다. 그가 제시한 유명한 내용중 하나가 오일러 경로와 순회이다.

오일러 경로(Euler tour(path)): 어떤 그래프의 모든 간선을 정확하게 한 번씩만 지나가는 경로
오일러 순회(Euler cycle(circuit)): 어떤 그래프의 모든 간선을 정확하게 한 번씩만 지나 시작점으로 다시 돌아오는 경로

다시 말해 오일러 순회는 시작점과 끝점이 똑같은 오일러 경로이다. 한붓그리기의 대표적인 예시인 쾨니히스베르크 다리 건너기 문제가 유명하다.

---

TSP

해밀턴 경로(Hamiltonian Circuit)는 모든 정점을 한 번씩만 방문하고 시작점으로 돌아오는 경로를 말한다. 이는 TSP(Traveling Salesperson Problem)의 핵심 개념 중 하나이다.
TSP는 1800년대에 아일랜드의 수학자 윌리엄 로완 해밀턴에 의해 수학적으로 정의되었다. 이 문제는 조합 최적화 문제에서 NP-hard 문제이고 이는 다항시간내에 푸는 최적의 해를 찾는 것이 지금까지는 불가능 하다는 것을 의미한다.

Brute-force 기법을 보면 아래와 같이 n!의 시간복잡도를 같게 되기 때문에 현실적으로 풀이가 불가능한 문제가 된다.

TSP문제에 자주 쓰이는 용어를 보자.
V : 모든 정점의 집합이다.
A : V의 부분 집합이다.
D[v_i][A] = A에 속한 정점을 각각 한 번씩만 거쳐서 v_i 에서 v_1 로 가는 최단 경로의 길이이다.

예시 케이스를 통해 보자.

---

Example

아래와 같은 구조의 그래프형태에서 최적 경로를 찾아보자.

아래가 모든 연산을 진행한것이 아니다. 아래와 같은 연산을 모든 경우의 수에 대해 하나도 빠짐없이 전부 수행하여 최종 결과를 찾아내야한다.

해당 알고리즘의 pseudo code는 아래와 같다.

void travel(int n, const number W[], index P[][], number& minlength) {
  index i, j, k;
  number D[1..n][subset of V-{v1}];
  
  for(i=2; i<=n; i++)
    D[i][∅] W[i][1];
    
    for(k=1; k<= n-2; k++)
      for(all subsets A⊂V-{v1} containing k vertices)
        for(i such that i 1 and vi is not in A) {
          D[i][A] = min(W[i][j] + D[j][A-{vj}]);//(j:vj∈A) //basic operation
          P[i][A] = value of j that gave the minimum;
        }
     
      D[1][V-{v1}] = min(W[1][j]+D[j][V-{v1,vj}]);//2<=j<=n)
      P[1][V-{v1}] = value of j that gave the minimum;
      minlength = D[1][V-{v1}]
}

 

시간복잡도를 계산해보면 여전히 O(2^n)이다.

이를 실제로 대입해보면 20개 도시를 한 번씩만 모두 거쳐서 가장 빨리 다녀 올 수 있는 동선을 짤때 단위 연산 처리 시간을 1 𝜇𝑠 로 가정하면 Brute-force로 연산하였을 떄 19! 𝜇𝑠 = 3,857년이되고 DP로 연산했을 때 (20-1)(20-1)2^(20-1)𝜇𝑠 = 45초가 된다.

 

추가적으로 공간 복잡도 또한 O(2^n)이 된다. 배열 D[v_i][A] 와 P[vi][A]에 필요한 메모리를 계산해보자.  A 즉, V-{vi }의 부분 집합의 개수는 2n-1, |V-{vi }| = n-1이고 집합 X의 부분집합의 개수는 2|X|이므로 S(n) = 2 x n*2^(n-1) = n*2^n = O(n*2^n)이다.

---