Microsoft PowerPoint - 08_Dynamic_Prog_01.pptx

Size: px

Start display at page:

Download "Microsoft PowerPoint - 08_Dynamic_Prog_01.pptx"

령 궁
7 years ago
Views:

1 CSW3010 (Introduction to Computer Algorithms) 담당교수 : 임종석서강대학교컴퓨터공학과 Dynamic Programming ( 동적계획알고리즘 ) Optimization Problem 을해결하기위한알고리즘. Bottom-up Approach : 주어진 instance 에대하여 1. 크기가가장작은모든 sub-instance 들에대해해를각각구하여저장한다. 2. 다음크기가작은모든 sub-instance 들에대해해를구하여저장한다. 이를위하여사전에구한 sub-instance 들의해를이용한다. 3. 2의과정을원래주어진 instance에대한해를구할때까지계속반복한다. 실제해구하기 Bottom-up으로구한것은일반적으로 cost. Top-down으로실제해를구한다. 2

2 D&C Algorithm 과 Dynamic Programming D&C Algorithm A는 B와 C로분할되고,B는 D와 E로분할되며,C는 F와 G 로분할되었다 (D,E,F,G는각각더이상분할불가). D와 E의해를취합하여 B의해를구하고,F와 G의해를취합하여 C의해를구한다. 마지막으로 B와 C의해를취합하여 A의해를구한다. D&C Algorithm에서는 sub-instance의해를중복사용하지않는다. 3 D&C Algorithm 과 Dynamic Programming 동적계획알고리즘 먼저최소단위인 D, E, F, G의해를각각구한다. D, E, F (E, F, G) 의해를이용하여 B(C) 의해를구한다. Sub-instance의해를상위레벨에서중복사용할수있다. B 와 C 의해를구하는데 E, F 가공통으로필요. 그리고, sub-instance 들사이에의존적관계가존재하는데, 대부분의경우이관계가뚜렷하게보이지않아서 함축적인순서 (implicit order) 라고도한다. 4

3 All Pairs Shortest Path 이문제는각 vertex를시작점으로하여 Dijkstra의최단경로알고리즘을수행할수있다 O(n 3 ), where n = V. Warshall은 graph에서모든쌍의경로존재여부 (transitive closure) 를찾아내는 dynamic programming 알고리즘을제안했고, Floyd는이를변형하여모든 all pair shortest path를찾는알고리즘을개발하였다. Floyd algorithm의시간복잡도는 O(n 3 ) 으로 Dijkstra algorithm 을 (n-1) 번사용할때의시간복잡도와동일하다. 그러나 Floyd algorithm은매우간단하여 Dijkstra algorithm을사용하는것보다효율적이다. 5 Floyd Algorithm Design 동적계획알고리즘으로모든쌍최단경로문제를해결하려면먼저부분문제 (sub-instance) 들을찾아야한다. 이를위해일단그래프의점 (vertex) 의수가적을때를생각해보자. 그래프에 3개의점이있는경우, 점 i에서점 j까지의최단경로를찾으려면 2가지경로, 즉, 점 i에서점 j로직접가는경로와점 1을경유하는경로중에서짧은것을선택하면된다. 1 i j 6

4 Floyd algorithm의기본아이디어는경유가능한점들을 점 1로부터시작하여, 점 1과 2, 그다음엔점 1, 2, 3으로하나씩추가하여, 마지막에는점 1 n까지의모든점을경유가능한점들로하여, 모든쌍의최단경로의거리를계산하는것이다. 부분문제정의 ( 입력그래프의점을각각 1, 2, 3,, n 이라하자 ) D ijk = 점 {1, 2,, k} 만을경유하는, 점 i로부터점 j까지의모든경로중에서가장짧은경로의거리 점 1에서점 k까지의모든점들을경유할필요는없다. D ijk 는점i에서점 j 간의 edge (i,j) 의가중치일수도있다. 또한, 만일 k i, k j이고,k=0인경우, 점 0은그래프에없으므로어떤점도경유하지않는다는것을의미한다. 따라서 D ij0 은입력으로주어지는 edge (i,j) 의가중치이다. 7 크기가가장작은 sub-instance D ij1 은 i에서점 1을경유하여 j로가는경로와i에서 j로직접가는경로, 즉, 선분 (i,j), 중에서짧은거리이다. 따라서모든쌍 i와 j에대하여 D ij1 을계산하는것이가장작은부분문제들이다. 단,i 1, j 1이다. D i1 0 1 D 1j 0 i D ij 0 j D ij 1 8

5 Next Smallest Sub-instance 점 i에서점 2를경유하여 j로가는경로의거리와 D ij1 중에서짧은거리를D ij2 로정한다. 여기서, 점 2를경유하는경로의거리는 D i21 + D 2j1 이다. 모든쌍 i와 j에대하여 D ij2 를계산하는것이그다음으로큰부분문제들이다. 단,i 2, j 2이다. D i2 1 2 D 2j 1 i D ij 1 j D ij 2 9 General Case 점 i에서점 k를경유하여 j로가는경로의거리와 D k-1 ij 중에서짧은것을로정한다. 여기서, 점 k를경유하는경로의거리는 D k-1 ik + D k-1 kj 이고,i k, j k이다. D ik k-1 k D kj k-1 i j D ij k D ij k-1 이런방식으로 k 가 1 에서 n 이될때까지 D ijk 를계산해서, D ijn, 즉, 모든점을경유가능한점들로고려된모든쌍 i 와 j 의최단경로의거리를찾는방식이 Floyd 의모든쌍최단경로알고리즘이다. 10

6 Floyd Algorithm AllPairsShortest 입력 : 2차원배열 D, where, D[i,j] = edge (i,j) 의가중치. 만일 edge (i,j) 가존재하지않으면 D[i,j] =. 모든 i에대하여 D[i,i]=0. 출력 : 모든쌍최단경로의거리를저장한 2-d 배열 D. 1. for k = 1 to n 2. for i = 1 to n 3. for j = 1 to n 4. D[i,j] = min{ D[i,k] + D[k,j], D[i,j] }; D[i,k] k D[k,j] i old D[i,j] j new D[i,j] 11 Floyd Algorithm 의특징 Negative cost edge is allowed. However, the graph must have no cycle with negative cost. O(n 3 ) algorithm, where n is the number of vertices. 12

7 Running Example Initial Values of D[i][j] D Running Example (cont d) k=1(d[][] 값이갱신된것만 ) D D[4,2] = min{d[4,2], D[4,1]+D[1,2]} = min{, -2+4} = 2 D[4,3] = min{d[4,3], D[4,1]+D[1,3]} = min{, -2+2} = 0 14

8 Running Example (cont d) k=2(d[][] 값이갱신된것만 ) D D[1,5] = min{d[1,5], D[1,2]+D[2,5]} = min{,4+4}=8 D[5,3] = min{d[5,3], D[5,2]+D[2,3]} = min{, -3+1} = Running Example (cont d) k=3(d[][] 값이갱신된것만 ) D D[1,4] = min{d[1,4], D[1,3]+D[3,4]} = min{5, 2+1} = 3 D[1,5] = min{d[1,5], D[1,3]+D[3,5]} = min{,2+2}=4 D[2,1] = min{d[2,1], D[2,3]+D[3,1]} = min{,1+1}=2 D[2,4] = 2, D[2,5] = 3, D[5,1] = -1, D[5,4] =

9 Running Example (cont d) k=4(d[][] 값이갱신된것만 ) D D[2,1] = min{d[2,1], D[2,4]+D[4,1]} = min{2, 2 2} = 0 D[3,1] = min{d[3,1], D[3,4]+D[4,1]} = min{1, 1 2} = 1 D[5,1] = min{d[5,1], D[5,4]+D[4,1]} = min{ 1, 1 2} = 3 17 Running Example (cont d) k=5(d[][] 값이갱신된것만 ) D D[1,2] = min{d[1,2], D[1,5]+D[5,2]} = min{4, 4 3} = 1 D[3,2] = min{d[3,2], D[3,5]+D[5,2]} = min{3, 2 3} = 1 D[4,2] = min{d[4,2], D[4,5]+D[5,2]} = min{2, 2 3} = 1 18

10 Running Example (cont d) Final All Pair Distances D Finding the Actual Shortest Path Maintain P[i][j] which stores the highest index of the intermediate vertices if one exists. Otherwise, 0 (i.e. initially 0). The Algorithm 1. for k = 1 to n 2. for i = 1 to n 3. for j = 1 to n 4. if ( D[i,k] + D[k,j] < D[i,j] ) { 5. D[i,j] = D[i,k] + D[k,j]; 6. P[i][j] = k; // 추가 7. } 20

11 Finding the Actual Shortest Path Example : A Path Printing Function 1. void path ( index q, index r ) { 2. if ( P[q][r]!= 0 ) { 3. path( q, P[q][r] ); // print intermediate vertices // between q and P[q][r]. 4. print P[q][r]; 5. path( P[q][r], r ); // print intermediate vertices 6. } // between q and P[q][r]. 7. } If we want to print the shortest path from u to w, print u; path (u, w); print w; 21 Floyd Algorithm 의응용 맵퀘스트 (Mapquest), 구글 (Google) 웹사이트의지도서비스 자동차네비게이션서비스 지리정보시스템 (GIS) 에서의네트워크분석 통신네트워크와모바일통신분야 게임 산업공학, 경영공학의 Operations Research ( 운영연구 ) 로봇공학 교통공학 VLSI 디자인분야등 22

Dynamic Programming and Optimization Problems Steps for an algorithm using dynamic programming Definition : The principle of optimality is said to apply in a problem if an optimal solution to an

12 Dynamic Programming and Optimization Problems Steps for an algorithm using dynamic programming Definition : The principle of optimality is said to apply in a problem if an optimal solution to an instance of a problem always contains optimal solutions to all substances. Shortest Path If P(s,t) is a shortest path, P(s,w) and P(w,t) are also shortest path. The reverse is not true. That is, there may be a shortest path which does not contain w. s w t 23 In order to apply the principle of optimality, we need to show that the principle holds before assuming that an optimal solution can be obtained using dynamic programming. The case when the principle of optimality does not hold Longest simple path problem [v1, v3, v2, v4] is the longest simple path. However, [v1, v3] is not a longest simple path. [v1, v2, v3] is the longest simple path. 24

Matrix Multiplication [n n] [n n] matrix multiplication Multiplication : T(n) = n 3. Addition : T(n) = n 3. n 3 n 2 after a slight modification of the algorithm. How?

13 Matrix Multiplication [n n] [n n] matrix multiplication Multiplication : T(n) = n 3. Addition : T(n) = n 3. n 3 n 2 after a slight modification of the algorithm. How? Using the Strassen s Algorithm (D&C), we can do this in O(n 2.81 ) multiplications and additions/subtractions. 25 [p q] [q r] matrix multiplication The result is [p r] matrix. Needs pqr multiplications by using normal multiplication. Example : [10 20] [20 5] = [10 5] Needs = 1,000 multiplications. 26

14 Associative Law ( 결합법칙 ) A B C=(A B) C=A (B C) Not Commutative A B B A Multiplications Reduction A B C=[10 20] [20 5] [5 15] (A B) C=[10 5] [5 15] = = 1750 multiplications. A (B C) = [10 20] [20 15] = = 4500 multiplications. 27 Chained Matrix Multiplication Problem 연속된행렬들의곱셈에필요한최소곱셈횟수및행렬간의곱셈순서를찾는문제. Example 가능한모든순서를체크하여최소곱셈수를찾는경우 needs exponential time. 28

15 The principle of optimality applies in this problem. Any sub-order of an optimal order is also optimal. If A 1 ((((A 2 A 3 )A 4 )A 5 )A 6 ) is an optimal order, (A 2 A 3 )A 4 is also an optimal order for multiplying A 2 A 3 A Sub-Instances ( 부분문제들 ) 가장작은크기의부분문제 참고사항 이웃하는 행렬끼리만 곱할 수 있다. 예를 들어 A B C D E 계산에,B를건너뛰어서 A C를수행하거나, B와 C를건너뛰어서 A D를먼저계산할수없다. 따라서, 크기가 2인부분문제들은인접한행렬간의곱이 며, 이들모두에대한곱셈수를계산해두어야한다. 30

16 크기가 3, 4, 5 인부분문제 A B C D E 은크기가 2, 3, 4 인부분문제들의일부를사용하여계산하여야한다. 31 Algorithm Design We are to compute A 1 A 2 A n. Assume that dimension of A k is d k 1 d k for 1 k n. We define C[i][j] as C[i][j] = A i 부터 A j 까지곱하기위한최소곱셈수 ( i< j 인경우만 ). C[i][i] = 0. Any multiplication order can be partitioned into two sub-orders. For example, there are 5 cases if n=6. Therefore, the following recursive property holds: The optimal order is one of these. min 1,, 0, for 1. 32

17 C[i][j] Calculation (Diagonal Order) Set C[0][0]=C[1][1]= =C[n][n] = 0. Obtain C[1][2], C[2][3],,C[n 1][n]. Obtain C[1][3], C[2][4],,C[n 2][n]. Obtain C[1][4], C[2][4],,C[n 3][n], etc. And finally we get C[1][n]. L Diagonal order L = 1, 2,, n 1. For each L, calculate C[1][1+L], C[2][2+L],,C[i][j=i+L],, C[n L][n]. For C[i][j], we need k (= i to j 1), because min 1,. 33 More on Indexing L=1일때, i=1: j=i+l=1+1=2(a 1 A 2 를계산하기위하여 ), i=2: j=2+1=3(a 2 A 3 을계산하기위하여 ), i=n L =n 1: j = (n 1) + 1 = n (A n 1 A n 을계산하기위하여 ) 크기가 2인부분문제의수 :(n 1) 개. L=2 일때, i=1: j=i+l=1+2 = 3 (A 1 A 2 A 3 을계산하기위하여 ), i=2: j=2+2=4(a 2 A 3 A 4 를계산하기위하여 ), i=n L =n 2: j = (n 2)+2=n(A n 2 A n 1 A n 을계산하기위해 ) 크기 3인부분문제의수 :(n 2) 개 34

18 L=3 일때 A 1 A 2 A 3 A 4,A 2 A 3 A 4 A 5,,A n 3 A n 2 A n 1 A n 등을계산. 크기가 4인부분문제의수가 (n 3) 개 L=n 2 일때 2 개의부분문제 A 1 A 2... A n 1,A 2 A 3... A n 을계산. L=n 1 일때 i=1 이면 j=1+(n 1) = n 이므로, 주어진문제 A 1 A 2... A n 을계산. 35 Finding Minimum min 1,. 함축적순서 36

19 Algorithm 입력 :A 1 A 2 A n, where the dimension of A i is d i-1 d i,1 i n. 출력 : 입력의행렬곱셈에필요한원소의최소곱셈횟수. 1. for i=1ton 2. C[i,i] = 0 ; // initialization 3. for L=1ton 1 { // diagonal loop. 4. for i=1ton L { 5. j = i + L; 6. C[i,j] = ; 7. for k=itoj 1 { 8. temp = C[i,k] + C[k+1,j] + d i-1 d k d j ; 9. if (temp < C[i,j]) 10. C[i,j] = temp; } } } 11. return C[1,n]; 37 Time Complexity 3. for L=1ton 1 { // n 1 iterations 4. for i=1ton L { // n 1, n 2,, 2, 1 iterations 5. j=i+l; 6. C[i,j] = ; 7. for k=itoj 1 { // L iterations (1, 2,, n 1) 8. temp = C[i,k] + C[k+1,j] + d i-1 d k d j ; 9. if (temp < C[i,j]) 10. C[i,j] = temp; } } } 11. return C[1,n]; Lines 3~10 s total iterations n 1+2(n 2)+3(n 3)+ +(n 2)2+n 1= = = 1 / /6= /6 /3 /3 1 =O(n 3 ). 38

20 Printing the Optimal Order Maintain P[i,j] which stores the value of k that give minimum. Initially, P[i,j] = 0. The Algorithm 3. for L=1ton 1 { 4. for i=1ton L { 5. j = i + L; 6. C[i,j] = ; 7. for k=itoj 1 { 8. temp = C[i,k] + C[k+1,j] + d i-1 d k d j ; 9. if (temp < C[i,j]) 10. C[i,j] = temp; P[i,j] = k; } } } 11. return C[1,n]; 39 If P[i,j] = k, the order will be (A i,, A k )(A k+1,, A j ). Therefore we may use the following procedure: void order ( index i, index j ) { // T(n)= (n). if ( i == j ) print Ai ; // print Ai else { k = P[i, j]; print ( ; // print ( order ( i, k ); // print the first partition order ( k+1, j ); // print the second partition print ) ; // print ) } 40

21 Edit Distance ( 편집거리문제 ) 문서편집기를사용하는중에하나의스트링 (string, 문자열 ) S를수정하여다른스트링 T로변환시키고자한다. 이변환을위하여삽입 (insert), 삭제 (delete), 대체 (substitute) 등의연산을사용할수있다. Edit Distance ( 편집거리 ) S를 T로변환시키는데필요한최소의편집연산횟수. Example : S = strong, T = stone Edit distance is 4. Is this optimal? 41 Example : S = strong, T = stone Edit distance is 4. Edit distance is 2. 42

22 The Principle of Optimality An Example with Minimum Edit Distance (=5) d : deletion s : substitution i : insertion Edit distance from INTE to EXEC above is optimal. Otherwise, there would be smaller edit distance, which results in smaller total edit distance than 5. Therefore, we can informally say that the problem of finding the minimum edit distance satisfies the principle of optimality. 43 Sub-Instances ( 부분문제 ) strong 을 stone 으로편집하고자한다. 만일각접두부 (prefix) 에대해서, 예를들어, stro 를 sto 로편집할때의편집거리를미리알고있으면, 각스트링의나머지부분에대해서, 즉, ng 를 ne 로의편집에대해서편집거리를찾음으로써, 주어진입력에대한편집거리를구할수있다. 44

23 스트링 S 와 T 의길이가각각 m 과 n 이라하고,S 와 T 의각문자를 s i 와 t j 라고하자 (i = 1, 2,, m, and j = 1, 2,,n). S=s 1 s 2 T=t 1 t 2 s i s m t j t n E[i, j] 를 S 의접두부의 i 개문자를 T 의접두부 j 개문자로변환시키는데필요한최소 edit distance 라고하자. Example : S = strong, T = stone E[2, 0] = st 를 null string으로바꾸기위한최소편집거리. E[0, 3] = null string을 sto 로바꾸기위한최소편집거리. E[2,0] = 2 (deletion 두번 ), E[0,3] = 3 이다 (insertion 세번 ). E[4, 3] = stro 를 sto 로바꾸기위한최소편집거리. E[6, 5] = S를 T로바꾸기위한최소편집거리. 45 Algorithm Design Example E[i, 0] = i and E[0, j] = j. E[1,1] = 0. No operation is needed ( s s ). E[1,2] = 1. One insertion is needed ( s st ). E[2,1] = 1. One deletion is needed ( st s ). E[2,2] = 0. No operation is needed ( st st ). 다음과같은세경우중하나 ( 최소값 ) 로생각할수있다. s st 수행후 s 2 = t 삭제. E[1,2] + 1 = 2. st s 수행후 t 2 = t 삽입. E[2,1] + 1 = 2. s s 수행후 no operation(s 2 =t 2 이므로 ). E[0,0] + 0 = 0. 46

24 Algorithm Design (cont d) E[4,3] ( 즉, stro sto 를위한최소편집거리 ) 세가지경우를생각할수있다. stro st 를수행하고,t 3 = o 추가. E[4,2] + 1. str sto 를수행하고,s 4 = o 삭제. E[3,3] + 1. str st 를수행하고, t4 = s3 이면 no operation. E[3,2] + 0. t4 s3 이면 substitution. E[3,2] + 1 ( 이예는해당안됨 ). 따라서, E[4,3] = min{e[4,2]+1, E[3,3]+1, E[3,2]+ (=0)}. 결론적으로, E[4,2], E[3,3], E[3,2] 를미리계산해두면 E[4,3] 를계산할수있다. 47 일반적으로 E[i 1,j],E[i,j 1], E[i 1, j 1] 의해가미리계산되어있으면 E[i, j] 를계산할수있으며, 다음과같이부분문제간의함축적인순서가있다. Recursive Property E[i, 0] = i, E[0, j] = j for i = 0, 1,, m and j = 0, 1,, n. Fori=1,2,,mandj=1,2,,n, E[i, j] = min {E[i 1, j] + 1,E[i,j 1] + 1,E[i,j]+ }, where =1ifs i t j,0otherwise. Insertion, deletion, substitution cost가각각다를경우위식에각operation에대응하는 cost로바꿔준다. 48

25 Indexing For E[i, j], we need E[i 1, j], E[i, j 1] and E[i, j]. Therefore, indexing by row-wise order is enough i E T ε s j t o n e S ε s 1 1 t 2 2 (i-1, j-1) (i-1, j) r 3 3 (i, j-1) (i, j) o 4 4 n 5 5 g 6 6 : empty string 49 Algorithm 입력 : 스트링 S, T, 단,S와T의길이는각각 m과 n이다. 출력 :S를T로변환하는편집거리, E[m,n] 1. for i=0 to m E[i,0]=i ; // 0번열의초기화 2. for j=0 to n E[0,j]=j ; // 0번행의초기화 3. for i=1 to m 4. for j=1 to n 5. E[i, j] = min{e[i, j 1]+1, E[i 1, j]+1, E[i 1, j 1]+α} 6. return E[m,n] Time Complexity = O(nm). 50

26 Example E T ε s t o n e S ε s i t r 3 3 2? o 4 4 n 5 5 g 6 6 j Since s 3 (= r ) t 2 (= t ), α =1. E[3, 2] = min{e[3, 1]+1, E[2, 2]+1, E[2, 1]+α} = min{3, 1, 2} =1=E[2, 2] + 1 (i.e., delete s 3 (= r )). 51 Finding the Operations Operation applied can be obtained by backtracking. Final Result of Our Example E T ε s t o n e j S i ε s t r o n g if α = 1 substitute t j else nop delete s i (i-1,j-1) (i-1,j) (i,j-1) insert t i minimum edit distance (i,j) 52

27 At (6, 5) α = 1, and hence E[6,5]=min{ 3, 3, 2 } Therefore, E[6,5] is from E[5,4] substitution ( g e ) E T ε s t o n e j S i ε s t r o n g if α = 1 substitute t j else nop delete s i (i-1,j-1) (i-1,j) (i,j-1) insert t i minimum edit distance (i,j) 53 At (5, 4) α = 0, and hence E[5,4]=min{ 3, 3, 1 } Therefore, E[5,4] is from E[4,3] no operation. E T ε s t o n e j S i ε s t r o n g At (4, 3) : no operation if α = 1 substitute t j else nop delete s i (i-1,j-1) (i-1,j) (i,j-1) insert t i (i,j) 54

28 At (3, 2) α = 1, and hence E[3,2]=min{ 3, 1, 2 } Therefore, E[3,2] is from E[2,2] delete s 3 = r. E T ε s t o n e j S i ε s t r o n g if α = 1 substitute t j else nop delete s i (i-1,j-1) (i-1,j) (i,j-1) insert t i (i,j) 55 At (2, 2) α = 0, and hence E[2,2]=min{ 2, 2, 0 } Therefore, E[2,2] is from E[1,1] no operation E T ε s t o n e j S i ε s t r o n g At (1, 1), no operation. if α = 1 substitute t j else nop delete s i (i-1,j-1) (i-1,j) (i,j-1) insert t i (i,j) 56

29 Edit Distance Problem 의응용 2개의스트링사이의편집거리가작으면, 이스트링들이서로유사하다고판단할수있으므로, 생물정보공학 (Bioinformatics) 및의학분야에서두개의유전자가얼마나유사한가를측정하는데활용된다. 철자오류검색 (Spell Checker), 광학문자인식 (Optical Character Recognition) 에서의보정시스템 (Correction System), 자연어번역 (Natural Language Translation) 소프트웨어등에도활용된다. 57

Let G = (V, E) be a connected, undirected graph with a real-valued weight function w defined on E. Let A be a set of E, possibly empty, that is includ

Let G = (V, E) be a connected, undirected graph with a real-valued weight function w defined on E. Let A be a set of E, possibly empty, that is includ 알고리즘설계와분석 (CSE3081(2 반 )) 기말고사 (2016년 12월15일 ( 목 ) 오전 9시40분 ~) 담당교수 : 서강대학교컴퓨터공학과임인성 < 주의 > 답안지에답을쓴후제출할것. 만약공간이부족하면답안지의뒷면을이용하고, 반드시답을쓰는칸에어느쪽의뒷면에답을기술하였는지명시할것. 연습지는수거하지않음. function MakeSet(x) { x.parent