6-5강 - Dynamic Programming 5 (The Traveling Salesperson Problem, TSP)

5. The Traveling Salesperson Problem (TSP)

0) The Traveling Salesperson Problem 

1> tour (Hamiltonian cycle)

모든 vertex를 한 번씩 지나는 cycle 구하기

2> optimal tour 

minimum length(cost)로 tour를 만들기

=> TSP : optimal tour 찾기

1) The Principle of Optimality

1> 전제 : T = [v1, vp1, vp2, ... , vpn-1, v1] = optimal tour

=> P = [vp1, vp2, ... , vpn-1, v1]라는 path가 minimum length(cost)

2> 가정 : P'라는 다른 path가 length(cost)가 더 작다.

3> 전제 부정 : P가 minimum length(cost)라는 것에 모순이 생깁니다.

4> 결론 : 그러므로 P가 minimal length(cost)를 가집니다.

 

2) Algorithm

0> recursive form을 위한 정의

W[i][j] : v_i부터 v_j까지의 length(cost) (edge가 없으면 ∞)

D[v_i][A] : [1] v_i부터 v₁까지 [2] A 내부의 모든 점을 한 번씩 지나는 [3] 최소 path의 length(cost)

 

1> recursive form

[1] recursive form

(vi에서 A 내부 원소들을 중복 없이 다 거쳐서 v1까지 갈 때의 minimum length)

- <1> vj에서 'vj를 제외한 A 내부 원소들을 중복 없이 다 거쳐서 v1까지 간 것 앞에

- <2> vi에서 vj까지의 length를 붙인 것

- A 내부의 j 중에서 <1> + <2>가 최소가 되는 것을 고른다.

 

 

[2] 초항

(vi에서 v1까지 아무것도 거치지 않고 갈 때의 minimum length = W[i][1])

 

[3] 최종 optimal tour 형태

(v1에서 V-{v1} 내부 원소들을 중복 없이 다 거쳐서 v1까지 갈 때의 minimum length)

 

2> bottom-up

A가 공집합일 때부터 |A|=n-1일 때까지 bottom-up

3> top-down

[1] memo 

P[i][A] : D[i][A}에서 최소를 만드는 j를 저장합니다. (i 다음에 i를 이어주는 j를 저장합니다.)

 

[2] 구현

3) Complexity

1> Time Complexity

2> Space Complexity