Dynamic Programming

Dijkstra’s Algorithm Goal: Find the shortest path from s to t 2 3 s 6 24 3 9 s 18 14 2 6 6 4 30 19 11 15 5 5 6 20 16 t 7 44

       S = { } PQ = { s, 2, 3, 4, 5, 6, 7, t } 2 3 s 6 4 5 t 7 24 3 9 s 18 14  2 6 6  4 30  19 11 15 5 5 6 20 16 t 7 44  

9 14 15        S = { s } PQ = { 2, 3, 4, 5, 6, 7, t } X 2 3 s X 24 3 9 s 18 14  X 14 2 6 6  30  4 19 11 15 5 5 6 20 16 t 7 44   15 X

9 14 15        S = { s, 2 } PQ = { 3, 4, 5, 6, 7, t } X 2 3 s X 24 3 9 s 18 14  X 14 2 6 6  30  4 19 11 15 5 5 6 20 16 t 7 44   15 X

9 15        S = { s, 2 } PQ = { 3, 4, 5, 6, 7, t } X 33 X 2 3 s 24 3 9 s 18 14  X 14 2 6 6  30  4 19 11 15 5 5 6 20 16 t 7 44   15 X

32 9 14 15        S = { s, 2, 6 } PQ = { 3, 4, 5, 7, t } X 33 X 24 3 9 s 18 14  X 14 2 6 6  44 30  X 4 19 11 15 5 5 6 20 16 t 7 44   15 X

9 14 15     X    S = { s, 2, 6, 7 } PQ = { 3, 4, 5, t } 32 X 33 24 3 9 s 18 14  X 14 2 6 6  44 X 35 30  X 4 19 11 15 5 5 6 20 16 t 7 44  15 59  X X

32 9 14 35 15        S = { s, 2, 3, 6, 7 } PQ = { 4, 5, t } X X 24 3 9 s 18 14  X 14 2 6 6 35  4 30  X 19 11 15 5 5 6 20 16 t 7 44 51   15 X X X

S = { s, 2, 3, 5, 6, 7 } PQ = { 4, t } 32  X 9 2 24 3 9 s 18 14  X 14 2 6 6 45  X 34 4 30 19 11 15 5 5 6 20 16 t 7 44 50  15 X

S = { s, 2, 3, 4, 5, 6, 7 } PQ = { t } 32  X 9 2 24 3 9 s 18 14  X 14 2 6 6 45  X 34 4 30 19 11 15 5 5 6 20 16 t 7 44 50  15 X

Dynamic Programming In mathematics and computer science, dynamic programming is a method of solving complex problems by breaking them down into simpler steps - wikipedia

Algorithms Review Backtracking Greedy Algorithm Dynamic Programming search every possible solution optimal guaranteed inefficient Greedy Algorithm find the best at each stage – MST not always optimal needs a proof Dynamic Programming efficient recursive algorithm

Recursive Algorithm Divide-and-Conquor Dynamic Programming top-down solution Fibonnaci can be inefficient duplicated computations Dynamic Programming bottom-up recursive and solve above limitations Fibonacci calculate F(1), F(2), .... and store the results use them to calculate F(n) F(n) = F(n-1) + F(n-2) = {F(n-2)+F(n-3)} + {F(n-3)+F(n-4)} = [{F(n-3)+F(n-4)}+{F(n-4)+F(n-5)}] +[{F(n-4)+F(n-5)}+{F(n-5)+F(n-6)}] = ...

Binomial Coefficient Redundancy ! n k n - 1 k - 1 n - 1 k = + int bino(int n, int k) { if (k==0 || n==k) return 1; else return bino(n-1, k-1) + bino(n-1, k); } {bino(n-2, k-2) + bino(n-2, k-1)} + {bino(n-2, k-1) + bino(n-2, k)} Redundancy !

Binomial Coefficient (2) kC0 = kCk = 1 2C1 = 1C0 + 1C1 3C1 = 2C0 + 2C1 3C2 = 2C1 + 2C2 4C1 = 3C0 + 3C1 4C2 = 3C1 + 3C2 ... ... ... ... 1 2 3 4 6 bino(int n, int k) { long bc[n][k]; for( int i=0; i<=n; i++) for( int j=0; j<=min(i,k); j++ ) if( j==0 || j==i ) bc[i][j]=1; else bc[i][j] = bc[i-1][j-1] + bc[i-1][j]; return bc[n][k]; }

Floyd’s Algorithm find all pairs shortest paths Floyd Alg. apply Dijkstra alg. for each vertex inefficient Floyd Alg. number each vertex from 1 to n start from W(0)=W, ends with W(n) which is a set of shortest paths – bottom up compute W(k) from W(k-1) - recursion typical dynamic programming problem

Floyd’s Algorithm W(k)[i][j] Adjacent Matrix: W shortest path from vi to vj the path traverses vertices among {v1, v2, ... , vk} 1 v1 v2 9 3 5 1 3 v5 v4 2 v3 3 4

Floyd’s Algorithm W(k)[i][j] = min(W(k-1)[i][j], W(k-1)[i][k]+W(k-1)[k][j]) shortest path from vi to vj using {v1, v2, … , vk} Case 1: the path does not visit vk Ex) W(5)[1][3] = W(4)[1][3] = 3 Case 2: the path visits vk Ex) W(2)[5][3] = W(1)[5][2] + W(1)[2][3] = 4+3 = 7 Case 1 Case 2

플로이드 알고리즘 <4> 데이터 구조 초기화 인접배열

플로이드 알고리즘 <5> 재귀 관계식 계산 W(k)[i][j] = min(W(k-1)[i][j], W(k-1)[i][k]+W(k-1)[k][j])

String Matching Edit Distance number of any following costs to make two strings match subs – match insertion deletion after any above operation, you are given shorter strings to match

delete remaining tail of t the characters match or substitute to make them match – i-1 and j-1 insert a char to s – append the last char of t to s, so compare s with t[0:n-1] delete a char from s – s is shorter, t is the same

Algorithm Review The number of function call grows exponentially The maximum number of distinct function call is Let’s make a table like .... the number of unique function calls is |s| * |t|

cell[i, j] means cost to make two strings match s[0..i] and t[0..j] worst case: subs all chars – diagonal values are i computing a cell requires three cells

엘리베이터 최적화 <1> 엘리베이터 최적화 문제 소개 모든 사람들이 입력한 층에서 엘리베이터가 멈춘다면 최악의 경우, 모든 층에서 멈춰야 하는 경우가 발생하므로, 최적화가 필요하다. 탑승객들은 엘리베이터가 움직이기 전에 원하는 층을 입력한다. 엘리베이터가 멈추는 횟수는 k번으로 제한되어 있다고 가정. 계단을 올라가는 것과 내려가는 것 사이에 차이가 없다고 가정. 걸어 올라가거나 내려가는 사람 수가 같은 층이 여러 명 존재할 경우 가장 낮은 층에 세운다. 반드시 탑승객이 내리겠다고 한 위치에서만 서는 것은 아니다. 예) 27층과 29층에서 내리는 탑승객이 있을 경우 28층에서 멈출 수 있음. 문제의 목적은 걸어서 올라가거나 내려가야 하는 사람 수를 최소화할 수 있는 층에 멈추는 것이다. 이때, 사람 수를 최소화한다는 것은 걷는 비용의 최소화를 의미한다.

엘리베이터 최적화 <2> 동적 프로그래밍을 이용한 해결 방법 f2층 f1층 동적 프로그래밍은 재귀 알고리즘을 바탕으로 함을 생각하자. k번째 멈출 층을 결정하는 것은 k-1번째 멈추는 모든 가능한 풀이의 비용에 따라 결정할 수 있다. 우선, f1층에서 선 후에 f2층에서 서는 경우를 생각해 보자. 이때, f2층은 목적지가 f1층 이하인 탑승객과는 상관이 없다. 즉, 문제를 두 조각으로 나눌 수 있다. 이 부분에서 동적 프로그래밍을 사용할 수 있음을 알 수 있다. f2층에서 내릴 탑승객은 f1층 위의 탑승객들만 관계되어 있다. 물론 f1층과 f2층 사이의 탑승객들은 f1층 f2층 중에서 한 곳에 내릴 것이다. f2층 f1층

엘리베이터 최적화 <3> mi,j i층 까지, j번 멈추면서 모든 승객을 운반하기 위한 최소 비용을 mi,j으로 정의한다. 그렇다면, (j+1)번째 멈출 위치는 이전에 i층에서 j번째로 멈추는 층보다 높으며, 이것은 i층보다 위로 올라갈 사람에게만 유효하다. 즉, 어느 층이 더 가까운지를 바탕으로 새로 멈추게 될 층과 i층에서 내릴 승객 으로 나눠야 한다. j+1번째 stop! ?층 i층 k층 j번 이동

엘리베이터 최적화 <3> mi,j=min{k=0…i-1}{mk,j-1 - walk(k,∞)+walk(k,i)+walk(i,∞)} 마지막으로 (j번째) 멈춘 층이 i층이었다면, 그 전에 (j-1번째) 멈췄던 층은 i층보다 작은 어떤 k층이었다. 그렇다면, mi,j은 mk,j-1로부터 k층 위로 올라가는 모든 승객에 대한 비용(walk(k,∞)) 을 빼고, i층에 멈추는 비용(walk(k,i)+walk(i,∞))을 더하면 된다. 이 문제를 해결하는데 있어 가장 중요한 것은 a층에서 멈춘 다음 b층에서 멈출 때, 승객들이 걸어서 이동한 층수의 총합을 계산하는 walk(a,b) 함수이다. walk(i,∞) walk(k,∞) j번째 stop! i층 k층 walk(k,i) j-1번 이동

Similar Problems A numerical sequence is monotonically increasing if the ith element is at least as big as the (i − 1)st element. The maximum monotone subsequence problem seeks to delete the fewest number of elements from an input string S to leave a monotonically increasing subsequence. Thus a longest increasing subsequence of “243517698” is “23568.” Find the longest sequence of elephants whose weights are increasing but whose IQ’s are decreasing. Can this be done as a special case of edit distance?