[고급 알고리즘] Dynamic Programming: Travelling salesman problem

1. Travelling salesman problem

• 여러 도시들이 있고 한 도시에서 다른 도시로 이동하는 비용이 모두 주어졌을 떄,
• 모든 도시들을 단 한 번만 방문하고 원래 시작점으로 돌아오는데 드는 최소 거리 구하기

 

그래프 이론

• 각 변에 가중치가 주어진 완전 그래프에서 가장 작은 가중치를 가진 해밀턴 순환 구하기

 

2. brute-force (permutation. NP)

time complexity

• $O(n!)$

 

3. dynamic programming (Held-Karp algorithm) 

동작 원리

초기화

• 모든 도시를 1부터 n까지 번호 매기기
• 임의의 도시를 시작점으로 선택

 

상태 정의

• $g(S, e)$ : 출발지에서 S에 포함된 모든 도시를 거쳐 e에 도달하는 최단 경로의 길이

 

최솟값 계산 (재귀적. 최적성 원리)

• S에 두 개 이상의 원소가 있을 때,  모든 가능한 부분집합과 모든 가능한 종착점에 대해 이 과정을 반복
• ${\displaystyle g(S,e)=\min _{1\leq i\leq k}g(S_{i},s_{i})+d(s_{i},e)}.$

 

집합 S

• S에서 도시 si​를 제외한 나머지 도시들의 집합입니다.
• ${\displaystyle S_{i}=S\setminus \{s_{i}\}=\{s_{1},\ldots ,s_{i-1},s_{i+1},\ldots ,s_{k}\}}$

 

time complexity

$O(n^2*2^{n})$

 

부분집합의 수

• n-1개의 도시에 대한 모든 부분집합 : $2^{n-1}$

 

각 부분집합에 대한 계산

• $n-1^2$

 

space complexity

• $O(n*2^{n})$
• 모든 계산된 g(S,e) 값들을 저장하기 위한 공간

 

예시

${\displaystyle C={\begin{pmatrix}0&2&9&10\\1&0&6&4\\15&7&0&8\\6&3&12&0\end{pmatrix}}}$

• g(x, S) - 1에서 S에 포함된 모든 도시를 거쳐 x에 도달하는 최단 경로의 길이
• $C_{xy}$ - x부터 y까지의 거리
• p(x, S) - 최적경로로 x에 가기 직전에 방문한 도시

 

g(3,{2}) = c32 + g(2, ∅ ) = c32 + c21 = 7 + 1 = 8       p(3,{2}) = 2 

g(4,{2}) = c42 + g(2, ∅ ) = c42 + c21 = 3 + 1 = 4       p(4,{2}) = 2

 

 

 

 

 

출처

• Wiki - Travelling salesman problem
• Wiki - Held–Karp algorithm