Travelling salesman problem - TSP

TSP :
N개 도시가 있고, 세일즈맨은 1번 도시에서 부터 시작해서 모든 도시를 한번씩만 거쳐서 다시 1번 도시로 돌아와야 한다. 각 도시를 이동할때의 비용이 있고-d(i,j)- 이때 최소 비용을 구하는 문제다.

naive :
기본적으로 N개의 도시를 차례대로 나열하는 Permutation 문제라고 볼 수 있다. 따라서 이때의 time complexity는 O(n!) 가 된다. N이 10정도만 되어도 문제 풀기 쉽지 않은 수준이다. (10! = 3628800)

DP :
C(i, S) : 1에서 시작해서 집합S에 있는 모든 도시를 한번씩만 거치고 i 도시로 들어오는 최소 비용
이라고 정의하면,
그러면 우리가 구하고자 하는 값은
C(1, S-{1}) 이 된다.

그 다음은 이렇게 된다.

C(i, {2..N}) =  min << C( j, {2..N} - {j}) + d(j, i) >> where 2<=j<=N, i!=j,  

C(1, {2..N})  이 우리가 원하는 최종답이 된다.

C(i, {}) = d(1,i) 단, i!=1
C(i, {2}) = C(2, {}) + d(2,i)
C(i, {3}) = C(3, {}) + d(3,i)
...
C(i, {2,3}) = min << C(2, {3}) + d(2,i)  or C(3, {2}) + d(3,i) >>
...
이런식으로 C(1, {2..N}) 을 구하게 된다.

그림으로..

집합S를 캐쉬로 표현할때는 bit 로 포함되고 안되고를 표현하면 되는데,
예를 들면, N=4 일때 {2,3,4} 를 표현하면 2^4-2 가 된다. 즉. 1110 (0은 1이 포함되지 않았다는 의미이다)

나중에 어떤 순서로 도시를 방문하는지 알고 싶으면 parent[S] 를 저장하고 있으면 된다.

나의 구현은 여기에

reference ::
https://github.com/evandrix/SPOJ/blob/master/DP_Main112/Solving-Traveling-Salesman-Problem-by-Dynamic-Programming-Approach-in-Java.pdf
https://www.youtube.com/watch?v=aQB_Y9D5pdw

Dynamic Programming - Knapsack

문제:

S 사이즈 만큼 담을 수 있는 가방이 있고, N개의 물건이 있다. 각 물건은 사이즈 s[i]와 가치 v[i]를 가진다. 가방안에 물건을 담을때 담을 수 있는 최대 가치는 얼마인가?

recurrence 식 추리:
일단 N개의 아이템이 있으니 prefix or suffix기반의 변수가 하나 필요하고(i), v의 최대값을 구하는 것이니 recurrence식의 인자로 v는 제외. 그럼 나머지는 S 밖에 없으니 그것을 두번째 인자로 하면 된다.

K(i, S ) = max{ K(i+1,S) , K(i+1, S-s[i]) + v[i]}

base cases:
K(i, 0) =0 , 0<=i<=N-1
K(N, i) = 0,  0<=i<=S

topological order:
i : N->0 로
S : 0->S or S->0 ; 즉 어느 순서로 해도 상관이 없다.

이 것을 2D 그림으로 표현해 보면 이렇게 된다.

역시 github에 코드를 반영해 놨으니 참고.

Dynamic Programming - intro

dynamic programming은
- careful brute force
- recursion + re-use
- shortest path in DAG
라고 볼 수 있다.


5 easy steeps to DP :

1. define subproblems
2. guess
1. guessing which subproblem to use to solve bigger problem
2. add more problems to guess/remember more
3. recurrence
4. recurse + memorize (acyclic인지 확인 필요)
   or bottom-up table (topological order를보고 bottom-up일지 top-down일지를 결정)
5. original problem

subproblem for strings/sequences 는 셋중 하나, 요 세개는 많이 쓰는 애들이니까 DP를 풀때 제일 먼저 생각해봐야 할 것들.

- suffix[i:]
- prefix[:i]
- substring[i:j]

이 교수님 강의 넘 맘에 든다. 귀에 쏙쏙. 4편까지 있음. 

씨리즈로 몇가지 문제를 풀어볼 생각이다.
DP 문제는 table 혹은 recursive 방식으로 모두 풀수 있다. recursive방식은 간단한 반면 탐색범위가 커지면 stack overflow로 한계가 있으므로 문제를 보고 탐색 범위를 보고 더 효율적인 방법으로 풀면 된다.

• Parenthesization
• Edit distance
• Knapsack
• Travelling Salesman problem