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
- 를 제외한 나머지 도시들의 집합입니다. 에서 도시
- ${\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
출처
'Algorithm' 카테고리의 다른 글
[고급 알고리즘] Greedy: Activity Selection Problem (0) | 2024.09.20 |
---|---|
[알고리즘] Range: Sliding Window (0) | 2024.09.19 |
[고급 알고리즘] Dynamic Programming: Longest Common Subsequence (0) | 2024.03.01 |
[고급 알고리즘] Dynamic Programming: Knapsack Problem (0) | 2024.03.01 |
[고급 알고리즘] Dynamic Programming: Fibonacci (0) | 2024.03.01 |