Dynamic Programming技术.ppt

1、1,第四章 Dynamic Programming技术,邹权（博士） 计算机科学系,2,4.1 Introduction,F(n) =,1if n = 0 or 1 F(n-1) + F(n-2)if n 1,Pseudo code for the recursive algorithm: F(n) 1if n=0 or n=1 then return 1 2elsereturn F(n-1) + F(n-2),Fibonacci number F(n),3,The execution of F(7),F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F0,F1,F2,F

2、1,F0,F2,F1,F0,F2,F1,F0,F4,F4,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,F1,4,The execution of F(7),Computation of F(2) is repeated 8 times!,F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F0,F1,F2,F1,F0,F2,F1,F0,F2,F1,F0,F4,F4,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,F1,5,The execution of F(7),Computation

3、 of F(3) is also repeated 5 times!,F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F0,F1,F2,F1,F0,F2,F1,F0,F2,F1,F0,F4,F4,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,F1,6,The execution of F(7),Many computations are repeated! How to avoid this?,F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F0,F1,F2,F1,F0,F2,F1,F0,F2,F1,F

4、0,F4,F4,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,F1,7,Idea for improvement,Memorization Store F1(i) somewhere after we have computed its value Afterward, we dont need to re-compute F1(i); we can retrieve its value from our memory.,F1(n) 1 if vn 0 then 2 vn F1(n-1)+F1(n-2) 3 return vn,Main() 1 v0

5、 = v1 1 2 for i 2 to n do 3 vi = -1 4 output F1(n),8,Look at the execution of F(7),v0 v1 v2 v3 v4 v5 v6 v7,F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F0,F1,F2,F1,F0,F2,F1,F0,F2,F1,F0,F4,F4,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,F1,F(i)=Fi,9,Look at the execution of F(7),v0 v1 v2 v3 v4 v5 v6 v7,F7,F6,

6、F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F0,F1,F2,F1,F0,F2,F1,F0,F2,F1,F0,F4,F4,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,F1,10,Look at the execution of F(7),v0 v1 v2 v3 v4 v5 v6 v7,F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F0,F1,F2,F1,F0,F2,F1,F0,F2,F1,F0,F4,F4,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,F1,11,

7、Look at the execution of F(7),v0 v1 v2 v3 v4 v5 v6 v7,F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F0,F1,F2,F1,F0,F2,F1,F0,F2,F1,F0,F4,F4,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,F1,12,Look at the execution of F(7),v0 v1 v2 v3 v4 v5 v6 v7,F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F0,F1,F2,F1,F0,F2,F1,F0,F2,F1,

8、F0,F4,F4,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,F1,13,Look at the execution of F(7),v0 v1 v2 v3 v4 v5 v6 v7,F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F0,F1,F2,F1,F0,F2,F1,F0,F2,F1,F0,F4,F4,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,F1,14,F1,F0,Look at the execution of F(7),v0 v1 v2 v3 v4 v5 v6 v7,

9、F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F2,F1,F0,F2,F1,F0,F2,F1,F0,F4,F4,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,F1,15,F1,F0,F2,F1,F0,F1,Look at the execution of F(7),F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F2,F1,F0,F2,F1,F0,F4,F4,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,v0 v1 v2 v3 v4 v5 v6 v7,16,

10、F1,F0,F2,F1,F0,F1,Look at the execution of F(7),F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F2,F1,F0,F2,F1,F0,F4,F4,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,v0 v1 v2 v3 v4 v5 v6 v7,17,F1,F0,F2,F1,F0,F2,F1,F0,F2,F1,F0,F3,F1,F1,Look at the execution of F(7),F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F4,F4,F3,F3,

11、F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,v0 v1 v2 v3 v4 v5 v6 v7,18,F1,F0,F2,F1,F0,F2,F1,F0,F2,F1,F0,F3,F1,F1,Look at the execution of F(7),F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F4,F4,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,v0 v1 v2 v3 v4 v5 v6 v7,19,F1,F0,F2,F1,F0,F2,F1,F0,F2,F1,F0,F3,F3,F3,F2,F1,F0,F2,F1,F0,

12、F2,F1,F0,F1,F1,F1,F1,Look at the execution of F(7),F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F1,F4,F4,v0 v1 v2 v3 v4 v5 v6 v7,20,F1,F2,F1,F0,F2,F1,F0,F2,F1,F0,F4,F3,F3,F3,F2,F1,F0,F2,F1,F0,F2,F1,F0,F1,F1,F1,F1,Look at the execution of F(7),F7,F6,F5,F5,F4,F3,F3,F2,F1,F0,F2,F0,F1,F4,v0 v1 v2 v3 v4 v5 v6 v7,21,

13、This new implementation saves lots of overhead.,Can we do even better?,Observation The 2nd version still make many function calls, and each wastes times in parameters passing, dynamic linking, . In general, to compute F(i), we need F(i-1) start filling the solution of the smallest problem. This ensu

14、res that when we solve a particular sub-problem, the solutions of all the smaller sub-problems that it depends are available.,For historical reasons, we call such methodology Dynamic Programming. In the late 40s (when computers were rare),programming refers to the tabular method.,24,Dynamic programm

15、ing VS Divide-and-conquer,Divide-and-conquer method 1. Subproblem is independent. 2. Subproblem is solved repeatedly. Dynamic programming (DP) 1. Subproblem is not independent. 2. Subproblem is just solved once. Common: Problem is partitioned into one or more subproblem, then the solution of subprob

16、lem is combined. DP reduces computation by Solving subproblems in a bottom-up fashion. Storing solution to a subproblem the first time it is solved. Looking up the solution when subproblem is met again.,25,26,4.2 Assembly-line scheduling,End,Sij :The jth station on line i ( i=1 or 2) . aij :The asse

17、mbly time required at station Sij. ei :Entry time. xi: Exit time.,27,One Solution,Brute force Enumerate all possibilities of selecting stations Compute how long it takes in each case and choose the best one Problem: There are 2n possible ways to choose stations Infeasible when n is large,28,fij = th

18、e fastest time to get from the starting point through station Sij Let f * denote fastest time to get a chassis all the way through the factory. j = 1 (getting through station 1) f11 = e1 + a11 f21 = e2 + a21,f * = min( f1n+x1 , f2n+x2 ),e1,e2,a11,a12,a13,a21,a22,a23,a1n-1,a1n,a2n-1,a2n,x1,x2,t1n-1,t

19、2n-1,Begin,Line 1,Line 2,t11,t21,t12,t22,29,2. A Recursive Solution (cont.),Compute fij for j = 2, 3, ,n, and i = 1, 2 Fastest way through S1j is either: fastest way through S1j-1then directly through S1j, or f1j = f1j - 1 + a1j fastest way through S2j-1, transfer from line 2 to line 1, then through

20、 S1j f1j = f2j -1 + t2j-1 + a1j f1j = min(f1j - 1 + a1j, f2j -1 + t2j-1 + a1j),a1j,a1j-1,a2j-1,t2j-1,S1j,S1j-1,S2j-1,30,The recursive equation For example, n=5: Solving top-down would result in exponential running time,f1j,f2j,1,2,3,4,5,f15,f25,f14,f24,f13,f23,2 times,4 times,f12,f22,f11,f21,31,3. C

21、omputing the Optimal Solution,For j 2, each value fij depends only on the values of f1j 1 and f2j - 1 Compute the values of fij in increasing order of j Bottom-up approach First find optimal solutions to subproblems Find an optimal solution to the problem from the subproblems,f1j,f2j,1,2,3,4,5,32,Ad

22、ditional Information,To construct the optimal solution we need the sequence of what line has been used at each station: lij the line number (1, 2) whose station (j - 1) has been used to get in fastest time through Sij, j = 2, 3, , n l* - the line whose station n is used to get in the fastest way thr

23、ough the entire factory,l1j,l2j,2,3,4,5,33,Step 3: Computing the fastest way,DPFastestWay(a, t, e, x, n) 1 f11 e1 + a11; f21 e2 + a21 2 for j 2 to n do 3 if f1j - 1 + a1j f2 j - 1 + t2j-1 + a1j then 4 f1j f1j - 1 + a1j 5 l1j 1 6 else f1j f2 j - 1 + t2j-1 + a1j 7 l1j 2 8 if f2j - 1 + a2j f1j - 1 + t1

24、j-1 + a2j then 9 f2j f2j - 1 + a2j 10 l2j 2 11 else f2 j f1j - 1 + t1j-1+ a2j then 12 l2j 1 13 if f1n + x1f2n + x2 then 14 f* f1n + x1 15 l* 1 16 else f* f2n + x2 17 l* 2,Running time: (n),34,For example,Begin,End,1,2,3,4,5,6,j,f1j,f2j,f *=38,9,12,18,16,20,22,24,25,32,30,35,37,2,3,4,5,6,j,l1j,l2j,l

25、*=1,2,1,1,1,1,1,2,2,2,2,35,4. Construct an Optimal Solution,PrintStations(l, n) 1 i l* 2 print “line ” i “, station ” n 3 for j n downto 2 do 4 i lij 5 print “line ” i “, station ” j - 1,line 1, station 6,line 2, station 5,line 2, station 4,line 1, station 3,line 2, station 2,2,3,4,5,6,j,l1j,l2j,l *

26、=1,2,1,1,1,1,1,2,2,2,2,line 1, station 1,36,2,4,3,2,7,9,4,4,8,8,5,4,7,5,2,3,3,4,2,1,2,1,3,6,1,2,Begin,End,The fastest assembly way,f *=38,37,4.3 Matrix-chain multiplication,Problem: Given a chain A1, A2, . . . , An of n matrices, where for i = 1, 2, . . . , n , matrix Ai has dimension pi-1 pi, fully

27、 parenthesize the product A1 A2.An in a way that minimizes the number of scalar multiplications. A1 A2 Ai Ai+1 An p0 p1 p1 p2 pi-1 pi pi pi+1 pn-1 pn A product of matrices is fully parenthesized if it is either a single matrix or the product of two fully parenthesized matrix products, surrounded by

28、parentheses.,38,For example, if the chain of matrices is , the product A1 A2 A3 A4 can be fully parenthesized in five distinct ways: (A1 (A2 (A3 A4) , (A1 (A2 A3) A4) , (A1 A2) (A3 A4) , (A1 (A2 A3) A4) , (A1 A2) A3) A4).,39,MatrixMultiply(A,B) 1 if mp then 2 print “Two matrices cannot multiply 3 el

29、se for i1 to n 4 for j1 to q do 5 Ci, j0 6 for k 1 to m do 7 Ci ,jCi ,j + Ai, k Bk, j 8 return C,Running time: (nmq),40,Consider the problem of a chain A1, A2, A3 of three matrices. Suppose that the dimensions of the matrices are 10100, 1005, and 550, respectively. 1. (A1A2) A3): A1A2 = 101005 = 5,0

30、00 (105) (A1 A2) A3) = 10550 = 2,500 Total: 7,500 scalar multiplications 2. (A1 (A2A3): A2A3 = 100550 = 25,000 (10050) (A1 (A2 A3) = 1010050 = 50,000 Total: 75,000 scalar multiplications one order of magnitude difference!,41,1. The structure of an optimal parenthesization,Notation: Aij = Ai Ai+1 Aj,

31、 i j For i j: Aij = Ai Ai+1 Aj = Ai Ai+1 Ak Ak+1 Aj = Aik Ak+1j,42,2. A recursive solution,Subproblem: determine the minimum cost of parenthesizing Aij = Ai Ai+1 Aj for 1 i j n Let mi, j = the minimum number of multiplications needed to compute Aij Full problem (A1.n): m1, n,43,2. A Recursive Soluti

32、on (cont.),Consider the subproblem of parenthesizing Aij = Ai Ai+1 Aj for 1 i j n = Aik Ak+1j for i k j mi, j = the minimum number of multiplications needed to compute the product Aij mi, j = mi, k + mk+1, j + pi-1pkpj,min # of multiplications to compute Aik,# of multiplications to compute AikAkj,mi

33、n # of multiplications to compute Ak+1j,44,2. A Recursive Solution (cont.),mi, j = mi, k + mk+1, j + pi-1pk pj We do not know the value of k There are ji possible values for k: k = i, i+1, , j-1 Minimizing the cost of parenthesizing the product Ai Ai+1 Aj becomes:,45,3. Computing the Optimal Costs,H

34、ow many subproblems do we have? Parenthesize Aij for 1 i j n One problem for each choice of i and j A recurrent algorithm may encounter each subproblem many times in different branches of the recursion overlapping subproblems Compute a solution using a tabular bottom-up approach, (n2),46,Reconstruct

35、ing the Optimal Solution,Additional information to maintain: si, j = a value of k at which we can split the product Ai Ai+1 Aj in order to obtain an optimal parenthesization,47,3. Computing the Optimal Costs (cont.),How do we fill in the tables m1.n, 1.n and s1.n, 1.n ? Determine which entries of th

36、e table are used in computing mi, j mi, j = cost of computing a product of j i 1 matrices mi, j depends only on costs for products of fewer than j i 1 matrices Aij = Aik Ak+1j Fill in m such that it corresponds to solving problems of increasing length,48,3. Computing the Optimal Costs (cont.),Length

37、 = 0: i = j, i = 1, 2, , n Length = 1: j = i + 1, i = 1, 2, , n-1,1,1,2,3,n,2,3,n,Compute rows from bottom to top and from left to right In a similar matrix s we keep the optimal values of k,i,j,49,MatrixChainOrder(p),DPMatrixChain(p) 1 for i 1 to n do 2 mi, i 0 3 for c 2 to n do 4 for i 1 to n c +

38、1 do 5 j i +c 1 6 mi, j 7 for k i to j 1 do 8 q mi, k + mk+1, j + pi-1pkpj 9 if q mi, j then 10 mi, j q; si, j k 11 return m and s,Running time: (n3),50,Example: min mi, k + mk+1, j + pi-1 pk pj,m2, 2 + m3, 5 + p1p2p5 m2, 3 + m4, 5 + p1p3p5 m2, 4 + m5, 5 + p1p4p5,1,1,2,3,6,2,3,6,i,j,4,5,4,5,m2, 5 =

39、min,Values mi, j depend only on values that have been previously computed,k = 2,k = 3,k = 4,51,Example: Compute A1A2A3,A1: 10100 (p0p1) A2: 1005 (p1p2) A3: 550 (p2p3) mi, i = 0 for i = 1, 2, 3 m1, 2 = m1, 1 + m2, 2 + p0p1p2 (A1A2) = 0 + 0 + 101005 = 5,000 m2, 3 = m2, 2 + m3, 3 + p1p2p3 (A2A3) = 0 +

40、0 + 100550 = 25,000 m1,1 + m2,3 + p0p1p3 = 75,000 (A1(A2A3) m1,2 +m3, 3 + p0p2p3 = 7,500 (A1A2)A3),1,1,2,2,3,3,m1,3 = min,52,4. Construct the Optimal Solution,Store the optimal choice made at each subproblem si, j = a value of k such that an optimal parenthesization of Ai.j splits the product betwee

41、n Ak and Ak+1 s1, n is associated with the entire product A1.n The final matrix multiplication will be split at k = s1,n A1.n = A1.s1, n As1, n+1.n For each subproduct recursively find the corresponding value of k that results in an optimal parenthesization,53,4. Construct the Optimal Solution (cont

42、.),si, j = value of k such that the optimal parenthesization of Ai Ai+1 Aj splits the product between Ak and Ak+1,1,1,2,3,6,2,3,6,i,j,4,5,4,5,s1,n=3 A1.6 = A1.3 A4.6 s1,3=1 A1.3 = A1.1 A2.3 s4,6=5 A4.6 = A4.5 A6.6,A1.n = A1.s1, n As1, n+1.n,54,4. Construct the Optimal Solution (cont.),1,1,2,3,6,2,3,

43、6,i,j,4,5,4,5,PrintParens(s, i, j) 1 if i = j then print “A”i 2 else print “(” 3 PrintParens(s, i, si, j) 4 PrintParens(s, si, j + 1, j) 5 print “)”,55,Example: A1 A6,1,1,2,3,6,2,3,6,i,j,4,5,4,5,PrintOPTParens(s, i, j) 1 if i = j then print “A”i 2 else print “(” 3 PrintOPTParens(s, i, si, j) 4 Print

44、OPTParens(s, si, j + 1, j) 5 print “)”,POP(s, 1, 6)s1, 6 = 3 i = 1, j = 6 “(“ POP (s, 1, 3) s1, 3 = 1 i = 1, j = 3 “(“ POP(s, 1, 1) “A1” POP(s, 2, 3) s2, 3 = 2 i = 2, j = 3 “(“ POP (s, 2, 2) “A2” POP (s, 3, 3) “A3” “)” “)”,(,(A4A5)A6),A1,(,A2,A3,),),(,s1.6, 1.6,56,4.4 The longest-common-subsequence

45、problem,Subsequence Common subsequence Maximum-length common subsequence Problem:Given two sequences Xm =and Yn = and wish to find a maximum-length common subsequence of Xm and Yn . E.g.: X = A, B, C, B, D, A, B Subsequences of X: A subset of elements in the sequence taken in order A, B, D, B, C, D,

46、 B, etc.,57,Example,X = A, B, C, B, D, A, B X = A, B, C, B, D, A, B Y = B, D, C, A, B, A Y = B, D, C, A, B, A B, C, B, A and B, D, A, B are longest common subsequences of X and Y (length = 4) B, C, A, however is not a LCS of X and Y,58,Brute-Force Solution,For every subsequence of Xm, check whether

47、its a subsequence of Yn There are 2m subsequences of Xm to check Each subsequence takes (n) time to check Scan Yn for first letter, from there scan for second, and so on Running time: (n2m),59,Notations,Given a sequence Xm = x1, x2, , xm we define the i-th prefix of Xm , for i = 0, 1, 2, , m Xi = x1

48、, x2, , xi ci, j = the length of a LCS of the sequences Xi = x1, x2, , xi and Yj = y1, y2, , yj,60,Step 1: Optimal substructure,Theorem (Optimal substructure of an LCS) Let Xm =and Yn = be sequences, and let Zk = be some LCS of Xm and Yn. 1. If xm = yn, then zk = xm = yn and zk-1 is an LCS of Xm-1 a

49、nd Yn-1. 2. If xm yn, and zk xm,then Zk is an LCS of Xm-1 and Yn. 3. If xm yn, and zk yn ,then Zk is an LCS of Xm and Yn-1.,61,Step 2: A recursive solution,Case 1: xi = yj e.g.: Xi = A, B, D, E Yj = Z, B, E Append xi = yj to the LCS of Xi-1 and Yj-1 Must find a LCS of Xi-1 and Yj-1 optimal solution

50、to a problem includes optimal solutions to subproblems,62,A Recursive Solution,Case 2: xi yj e.g.: Xi = A, B, D, G Yj = Z, B, D Must solve two problems find a LCS of Xi-1 and Yj: Xi-1 = A, B, D and Yj = Z, B, D find a LCS of Xi and Yj-1: Xi = A, B, D, G and Yj = Z, B Optimal solution to a problem in

51、cludes optimal solutions to subproblems,ci, j =,max ci - 1, j, ci, j-1 ,63,Overlapping Subproblems,To find a LCS of Xm and Yn We may need to find the LCS between Xm and Yn-1 and that of Xm-1 and Yn Both the above subproblems has the subproblem of finding the LCS of Xm-1 and Yn-1 Subproblems share su

52、bsubproblems,64,Step 3: Computing the Length of the LCS,0if i = 0 or j = 0 ci, j = ci-1, j-1 + 1if xi = yj max(ci, j-1, ci-1, j)if xi yj,yj:,xm,y1,y2,yn,x1,x2,xi,j,i,0,1,2,n,m,1,2,0,ci, j,65,Additional Information,0 if i, j = 0 ci, j = ci-1, j-1 + 1 if xi = yj max(ci, j-1, ci-1, j) if xi yj,yj:,D,A,

53、C,F,A,B,xi,j,i,0,1,2,n,m,1,2,0,A matrix bi, j: it tells us what choice was made to obtain the optimal value If xi = yj bi, j = “ ” Else, if ci - 1, j ci, j-1 bi, j = “ ” else bi, j = “ ”,3,3,C,D,b isolated difference: insertions, deletions, substitutions / rarely as one each hundred (100) characters

54、, to find the difference , two different sequencings (2)2 sequences 100s: whether a prefix similar to a suffix; if so, produced (3)2 sequences, is one is the subsequence of the other, to search certain sequence pattern (4)2 sequences : whether there are two similar substrings, one from each sequence

55、, similar, to analyze conservation sequence,77,comparing two sequences,alignments involving: global comparisons: entire sequences local comparisons: just substrings of sequences semiglobal comparisons: prefixes and suffixes dynamic programming (DP),78,global comparison- example,example of aligning G

56、ACGGATTAG GATCGGAATAG GA CGGATTAG GATCGGAATAG an extra T; a change from A to T; space: dash,79,global comparison- the basic algorithm,Definitions Alignment: insertion of spaces: same size creating a correspondence: one over the other Both space are not allowed (Spaces can be inserted in beginning or end) Scoring function : a measure of similarity between elements (nucleotides, amino acids, gaps); a match: +1/ identical characters a mismatch: -1/ distinct characters a space: