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 - Edit Distance

문제는
given two string x y, what's the cheapest possible sequence of char edits to turn x -> y
insert, delete, replace가 가능하고 각 edit의 cost는 정해져 있다.

예를 들어,
HIEROGLYPHOLOGY,  MICHAELANGELO 이 두 단어의 edit distance는 얼마일까?

우선 subproblem을 define해야 한다.
일단 스트링이 나오니까 prefix, suffix, substring중의 하나라고 볼 수 있다.
두개의 스트링이 나오니까 이들 2개의 조합일것이라 추측이 가능하다.

prefix 혹은 suffix기반의 recurrence식을 만들 수 있다.
prefix기반은 이렇게 된다.

유사하게 suffix 기반의 recurrence 식도 만들 수 있다. 이것은 여기서 설명하진 않고 github 소스에 구현되 있으므로 이를 참고하면 되겠다.


reference :
http://www.geeksforgeeks.org/dynamic-programming-set-5-edit-distance/

Dynamic Programming - Parenthesization

A[0] ... A[n-1] 의 N개의 matrix가 있고 A[0]*A[1]* ...A[n-1] 의 값을 구하는 효율적인 순서를 구하는 것이 문제.

Optimal evaluation of associative expression A[0]*A[n-1] e.g. multiplying rectangular matrices

A*B*C = (A*B)*C or A*(B*C)

인데
( m x l )* (l x n ) = (m x n matrix) 가 되고  첫 행렬의 렬(column) 과 두번째 행렬의 행(row)은 같아야 한다.
위의 경우 필요한 #multiplication = m*n*l 이 된다.

즉, (4 x 1)*(1 x 4)*(4 x 1) 을 생각해보면
 {(4 x 1)*(1 x 4)} * {(4 x 1)} = (4 x 4)*(4 x 1) 이지만
 (4 x 1)* {(1 x 4)*(4 x 1)} = (4 x 1)* 상수 가 된다.

이렇듯 순서에 따라서 더 작은 곱셈으로 답을 구할 수 있다.
이 문제는 어떤 순서로 계산을 하면 최대한 빨리 계산을 할 수 있는지를 물어보는 문제다.

앞서 썼던 Dynamic Programming - intro 에서 봤듯이 DP에서 제일 처음 풀어야 것은  subproblem을 정의 하는 것이다.

앞서 얘기한 부분을 잘 생각해보면 결국엔 outermost multiplication이 무엇이냐로 볼 수 있고
P(i,j)를 min cost from i to j
라고 define하면
recurrence는 이렇게 되고,
P(i,j) =  min { P(i,k) + P(k, j) + costOfMultiplication(A[i]~A[k]) by (A[k]~A[j]) } for k in range(i+1, j)

costOfMultiplication = A[i].row * A[j].col * A[k].col
( row 는 앞에 위치하는 행렬에서 결저이 되고 col은 뒤의 행렬에서 결정이 되므로 결국은 시작점의 row와 마지막 행혈의 col이 된다. )

P(i, i) = 0
이고

우리가 원하는 답은 P(0, n)이 된다.
여기서 좀 특이한 것은 topological order를 구하기가 좀 애매하다.

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