DynamicProgramming技术学习教程.pptx

《DynamicProgramming技术学习教程.pptx》由会员分享，可在线阅读，更多相关《DynamicProgramming技术学习教程.pptx（158页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、14.1 IntroductionF(n)=1if n=0 or 1F(n-1)+F(n-2)if n 1n012345678910F(n)1123581321345589Pseudo code for the recursive algorithm:F(n)1if n=0 or n=1 then return 12elsereturn F(n-1)+F(n-2)Fibonacci number F(n)第1页/共158页2The execution of F(7)F7F6F5F5F4F3F3F2F1F0F2F1F0F1F2F1F0F2F1F0F2F1F0F4F4F3F3F3F2F1F0F2F

2、1F0F2F1F0F1F1F1F1第2页/共158页3The execution of F(7)Computation of F(2)is repeated 8 times!F7F6F5F5F4F3F3F2F1F0F2F1F0F1F2F1F0F2F1F0F2F1F0F4F4F3F3F3F2F1F0F2F1F0F2F1F0F1F1F1F1第3页/共158页4The execution of F(7)Computation of F(3)is also repeated 5 times!F7F6F5F5F4F3F3F2F1F0F2F1F0F1F2F1F0F2F1F0F2F1F0F4F4F3F3F3

3、F2F1F0F2F1F0F2F1F0F1F1F1F1第4页/共158页5The execution of F(7)Many computations are repeated!How to avoid this?F7F6F5F5F4F3F3F2F1F0F2F1F0F1F2F1F0F2F1F0F2F1F0F4F4F3F3F3F2F1F0F2F1F0F2F1F0F1F1F1F1第5页/共158页6Idea for improvementMemorization Store F1(i)somewhere after we have computed its value Afterward,we do

4、nt need to re-compute F1(i);we can retrieve its value from our memory.F1(n)1 if vn 0 then2 vn F1(n-1)+F1(n-2)3 return vnMain()1 v0=v1 12 for i 2 to n do3 vi=-14 output F1(n)第6页/共158页7Look at the execution of F(7)11-1-1-1-1-1-1v0v1v2v3v4v5v6v7F7F6F5F5F4F3F3F2F1F0F2F1F0F1F2F1F0F2F1F0F2F1F0F4F4F3F3F3F2

5、F1F0F2F1F0F2F1F0F1F1F1F1F(i)=Fi第7页/共158页8Look at the execution of F(7)11-1-1-1-1-1-1v0v1v2v3v4v5v6v7F7F6F5F5F4F3F3F2F1F0F2F1F0F1F2F1F0F2F1F0F2F1F0F4F4F3F3F3F2F1F0F2F1F0F2F1F0F1F1F1F1第8页/共158页9Look at the execution of F(7)112-1-1-1-1-1v0v1v2v3v4v5v6v7F7F6F5F5F4F3F3F2F1F0F2F1F0F1F2F1F0F2F1F0F2F1F0F4F4

6、F3F3F3F2F1F0F2F1F0F2F1F0F1F1F1F1第9页/共158页10Look at the execution of F(7)112-1-1-1-1-1v0v1v2v3v4v5v6v7F7F6F5F5F4F3F3F2F1F0F2F1F0F1F2F1F0F2F1F0F2F1F0F4F4F3F3F3F2F1F0F2F1F0F2F1F0F1F1F1F1第10页/共158页11Look at the execution of F(7)1123-1-1-1-1v0v1v2v3v4v5v6v7F7F6F5F5F4F3F3F2F1F0F2F1F0F1F2F1F0F2F1F0F2F1F0F4

7、F4F3F3F3F2F1F0F2F1F0F2F1F0F1F1F1F1第11页/共158页12Look at the execution of F(7)1123-1-1-1-1v0v1v2v3v4v5v6v7F7F6F5F5F4F3F3F2F1F0F2F1F0F1F2F1F0F2F1F0F2F1F0F4F4F3F3F3F2F1F0F2F1F0F2F1F0F1F1F1F1第12页/共158页13F1F0Look at the execution of F(7)11235-1-1-1v0v1v2v3v4v5v6v7F7F6F5F5F4F3F3F2F1F0F2F1F2F1F0F2F1F0F2F1F0F

8、4F4F3F3F3F2F1F0F2F1F0F2F1F0F1F1F1F1第13页/共158页14F1F0F2F1F0F1Look at the execution of F(7)11235-1-1-1F7F6F5F5F4F3F3F2F1F0F2F1F2F1F0F2F1F0F4F4F3F3F3F2F1F0F2F1F0F2F1F0F1F1F1v0v1v2v3v4v5v6v7第14页/共158页15F1F0F2F1F0F1Look at the execution of F(7)112358-1-1F7F6F5F5F4F3F3F2F1F0F2F1F2F1F0F2F1F0F4F4F3F3F3F2F1F0

9、F2F1F0F2F1F0F1F1F1v0v1v2v3v4v5v6v7第15页/共158页16F1F0F2F1F0F2F1F0F2F1F0F3F1F1Look at the execution of F(7)112358-1-1F7F6F5F5F4F3F3F2F1F0F2F1F4F4F3F3F2F1F0F2F1F0F2F1F0F1F1v0v1v2v3v4v5v6v7第16页/共158页17F1F0F2F1F0F2F1F0F2F1F0F3F1F1Look at the execution of F(7)11235813-1F7F6F5F5F4F3F3F2F1F0F2F1F4F4F3F3F2F1F0

10、F2F1F0F2F1F0F1F1v0v1v2v3v4v5v6v7第17页/共158页18F1F0F2F1F0F2F1F0F2F1F0F3F3F3F2F1F0F2F1F0F2F1F0F1F1F1F1Look at the execution of F(7)11235813-1F7F6F5F5F4F3F3F2F1F0F2F1F4F4v0v1v2v3v4v5v6v7第18页/共158页19F1F2F1F0F2F1F0F2F1F0F4F3F3F3F2F1F0F2F1F0F2F1F0F1F1F1F1Look at the execution of F(7)1123581321F7F6F5F5F4F3F3

11、F2F1F0F2F0F1F4v0v1v2v3v4v5v6v7第19页/共158页20This new implementation saves lots of overhead.Can we do even better?ObservationThe 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)&F(i-2)onlyIdea to further im

12、proveCompute the values in bottom-up fashion.That is,compute F(2)(we already know F(0)=F(1)=1),then F(3),then F(4)F2(n)1 F0 12 F1 13 for i 2 to n do4Fi Fi-1+Fi-25 return Fn第20页/共158页21Recursive vs Dynamic programmingRecursive version:F(n)1if n=0 or n=1 then return 12elsereturn F(n-1)+F(n-2)Dynamic P

13、rogramming version:F2(n)1 F0 12 F1 13 for i 2 to n do4Fi Fi-1+Fi-25 return FnTooSlow!Efficient!Time complexity is O(n)第21页/共158页22Summary of the methodologyWrite down a formula that relates a solution of a problem with those of sub-problems.E.g.F(n)=F(n-1)+F(n-2).Index the sub-problems so that they

14、can be stored and retrieved easily in a table(i.e.,array)Fill the table in some bottom-up manner;start filling the solution of the smallest problem.This ensures that when we solve a particular sub-problem,the solutions of all the smaller sub-problems that it depends are available.For historical reas

15、ons,we call such methodologyDynamic Programming.In the late 40s(when computers were rare),programming refers to the tabular method.第22页/共158页23 Dynamic programming VS Divide-and-conquerDivide-and-conquer method 1.Subproblem is independent.2.Subproblem is solved repeatedly.Dynamic programming(DP)1.Su

16、bproblem is not independent.2.Subproblem is just solved once.Common:Problem is partitioned into one or more subproblem,then the solution of subproblem 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

17、 up the solution when subproblem is met again.第23页/共158页24第24页/共158页254.2 Assembly-line schedulingEndSij:The jth station on line i(i=1 or 2).aij:The assembly time required at station Sij.ei:Entry time.xi:Exit time.e1e2a11a12a13a21a22a23a1n-1a1na2n-1a2nx1x2t1n-1t2n-1BeginLine 1Line 2t11t21t12t22S11S1

18、2S13S1n-1S1nS21S22S23S2n-1S2n第25页/共158页26One SolutionBrute forceEnumerate all possibilities of selecting stationsCompute how long it takes in each case and choose the best oneProblem:There are 2n possible ways to choose stationsInfeasible when n is large100111 if choosing line 1 at step j(=n)1234n0

19、if choosing line 2 at step j(=3)第26页/共158页27fij=the fastest time to get from the starting point through station SijLet 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+a21f*=min(f1n+x1,f2n+x2)e1e2a11a12a13a21a22a23a1n-1a1na2n-1a2n

20、x1x2t1n-1t2n-1BeginLine 1Line 2t11t21t12t22第27页/共158页282.A Recursive Solution(cont.)Compute fij for j=2,3,n,and i=1,2Fastest way through S1j is either:fastest way through S1j-1then directly through S1j,or f1j=f1j-1+a1jfastest way through S2j-1,transfer from line 2 to line 1,then through S1j f1j=f2j-

21、1+t2j-1+a1jf1j=min(f1j-1+a1j,f2j-1+t2j-1+a1j)a1ja1j-1a2j-1t2j-1S1jS1j-1S2j-1第28页/共158页29The recursive equationFor example,n=5:Solving top-down would result in exponential running timef1jf2j12345f15f25f14f24f13f232 times4 timesf12f22f11f21第29页/共158页303.Computing the Optimal SolutionFor j 2,each value

22、 fij depends only on the values of f1j 1 and f2j-1Compute the values of fijin increasing order of jBottom-up approachFirst find optimal solutions to subproblemsFind an optimal solution to the problem from the subproblemsf1jf2j12345increasing j第30页/共158页31Additional InformationTo construct the optima

23、l 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,nl*-the line whose station n is used to get in the fastest way through the entire factoryl1jl2j2345increasing j第31页/共158页32Step

24、3:Computing the fastest wayDPFastestWay(a,t,e,x,n)1 f11 e1+a11;f21 e2+a212 for j 2 to n do3 if f1j-1+a1j f2 j-1+t2j-1+a1j then4 f1j f1j-1+a1j5 l1j 16 else f1j f2 j-1+t2j-1+a1j 7 l1j 28 if f2j-1+a2j f1j-1+t1j-1+a2j then9 f2j f2j-1+a2j 10 l2j 211 else f2 j f1j-1+t1j-1+a2j then 12 l2j 113 if f1n+x1f2n+

25、x2 then14 f*f1n+x115 l*116 else f*f2n+x2 17 l*2Running time:(n)第32页/共158页33For example24327944885475233421213612BeginEnd123456jf1jf2jf*=389121816202224253230353723456jl1jl2jl*=12111112222第33页/共158页344.Construct an Optimal SolutionPrintStations(l,n)1 i l*2 print“line”i“,station”n3 for j n downto 2 do

26、4 i lij5 print“line”i“,station”j-1line 1,station 6line 2,station 5line 2,station 4line 1,station 3line 2,station 223456jl1jl2jl*=12111112222line 1,station 1第34页/共158页3524327944885475233421213612BeginEndThe fastest assembly way f*=38第35页/共158页364.3 Matrix-chain multiplication Problem:Given a chain A1

27、,A2,.,An of n matrices,where for i=1,2,.,n,matrix Ai has dimension pi-1 pi,fully 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 m

28、atrix or the product of two fully parenthesized matrix products,surrounded by parentheses.第36页/共158页37For 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).第37页/共158页38Ma

29、trixMultiply(A,B)1 if mp then2 print“Two matrices cannot multiply 3 else for i1 to n 4 for j1 to q do5 Ci,j0 6 for k 1 to m do7 Ci,jCi,j+Ai,k Bk,j 8 return CRunning time:(nmq)第38页/共158页39Consider the problem of a chain A1,A2,A3 of three matrices.Suppose that the dimensions of the matrices are 10100,

30、1005,and 550,respectively.1.(A1A2)A3):A1A2=101005=5,000 (105)(A1 A2)A3)=10550=2,500Total:7,500 scalar multiplications2.(A1(A2A3):A2A3=100550=25,000(10050)(A1(A2 A3)=1010050=50,000Total:75,000 scalar multiplicationsone order of magnitude difference!第39页/共158页401.The structure of an optimal parenthesi

31、zationNotation:Aij=Ai Ai+1 Aj,i jFor i j:Aij=Ai Ai+1 Aj =Ai Ai+1 Ak Ak+1 Aj =Aik Ak+1j 第40页/共158页412.A recursive solutionSubproblem:determine the minimum cost of parenthesizing Aij=Ai Ai+1 Aj for 1 i j nLet mi,j=the minimum number of multiplications needed to compute AijFull problem(A1.n):m1,n第41页/共

32、158页422.A Recursive Solution(cont.)Consider the subproblem of parenthesizing Aij=Ai Ai+1 Aj for 1 i j n =Aik Ak+1j for i k jmi,j=the minimum number of multiplications needed to compute the product Aijmi,j=mi,k +mk+1,j +pi-1pkpjmin#of multiplications to compute Aik#of multiplications to compute AikAk

33、jmin#of multiplications to compute Ak+1jmi,kmk+1,jpi-1pkpj第42页/共158页432.A Recursive Solution(cont.)mi,j=mi,k +mk+1,j +pi-1pk pjWe do not know the value of kThere are ji possible values for k:k=i,i+1,j-1Minimizing the cost of parenthesizing the product Ai Ai+1 Aj becomes:第43页/共158页443.Computing the O

34、ptimal CostsHow many subproblems do we have?Parenthesize Aij for 1 i j nOne problem for each choice of i and jA recurrent algorithm may encounter each subproblem many times in different branches of the recursion overlapping subproblemsCompute a solution using a tabular bottom-up approach(n2)第44页/共15

35、8页45Reconstructing the Optimal SolutionAdditional 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第45页/共158页463.Computing the Optimal Costs(cont.)How do we fill in the tables m1.n,1.n and s1.n,1.n?Determine which en

36、tries of the table are used in computing mi,jmi,j=cost of computing a product of j i 1 matricesmi,j depends only on costs for products of fewer than j i 1 matrices Aij=Aik Ak+1jFill in m such that it corresponds to solving problems of increasing length第46页/共158页473.Computing the Optimal Costs(cont.)

37、Length=0:i=j,i=1,2,nLength=1:j=i+1,i=1,2,n-11123n23nfirstsecondCompute rows from bottom to top and from left to rightIn a similar matrix s we keep the optimal values of km1,n gives the optimalsolution to the problemij第47页/共158页49Example:min mi,k+mk+1,j+pi-1 pk pj m2,2+m3,5+p1p2p5m2,3+m4,5+p1p3p5m2,4

38、+m5,5+p1p4p511236236ij4545m2,5=min nValues mi,j depend only on values that have been previously computedk=2k=3k=4第49页/共158页50Example:Compute A1A2A3 A1:10100(p0p1)A2:1005 (p1p2)A3:550 (p2p3)mi,i=0 for i=1,2,3m1,2=m1,1+m2,2+p0p1p2(A1A2)=0+0+101005=5,000m2,3=m2,2+m3,3+p1p2p3 (A2A3)=0+0+100550=25,000 m1

39、,1+m2,3+p0p1p3=75,000 (A1(A2A3)m1,2+m3,3+p0p2p3=7,500 (A1A2)A3)0001122335000125000275002m1,3=min第50页/共158页514.Construct the Optimal SolutionStore the optimal choice made at each subproblemsi,j=a value of k such that an optimal parenthesization of Ai.j splits the product between Ak and Ak+1s1,n is as

40、sociated with the entire product A1.nThe final matrix multiplication will be split at k=s1,nA1.n=A1.s1,n As1,n+1.nFor each subproduct recursively find the corresponding value of k that results in an optimal parenthesization第51页/共158页524.Construct the Optimal Solution(cont.)si,j=value of k such that

41、the optimal parenthesization of Ai Ai+1 Aj splits the product between Ak and Ak+133355-3334-333-12-1-11236236ij4545s1,n=3 A1.6=A1.3 A4.6s1,3=1 A1.3=A1.1 A2.3s4,6=5 A4.6=A4.5 A6.6A1.n=A1.s1,n As1,n+1.n第52页/共158页534.Construct the Optimal Solution(cont.)33355-3334-333-12-1-11236236ij4545PrintParens(s,i

42、,j)1 if i=j then print“A”i2 else print“(”3 PrintParens(s,i,si,j)4 PrintParens(s,si,j+1,j)5 print“)”第53页/共158页54Example:A1 A633355-3334-333-12-1-11236236ij4545PrintOPTParens(s,i,j)1 if i=j then print“A”i2 else print“(”3 PrintOPTParens(s,i,si,j)4 PrintOPTParens(s,si,j+1,j)5 print“)”POP(s,1,6)s1,6=3i=1

43、,j=6 “(“POP(s,1,3)s1,3=1i=1,j=3 “(“POP(s,1,1)“A1”POP(s,2,3)s2,3=2i=2,j=3“(“POP(s,2,2)“A2”POP(s,3,3)“A3”“)”“)”(A4A5)A6)A1(A2A3)(s1.6,1.6第54页/共158页554.4 The longest-common-subsequence problemSubsequenceCommon subsequenceMaximum-length common subsequenceProblem:Given two sequences Xm=and Yn=and wish to

44、 find a maximum-length common subsequence of Xm and Yn.E.g.:X=A,B,C,B,D,A,BSubsequences of X:A subset of elements in the sequence taken in order A,B,D,B,C,D,B,etc.第55页/共158页56ExampleX=A,B,C,B,D,A,B X=A,B,C,B,D,A,BY=B,D,C,A,B,A Y=B,D,C,A,B,AB,C,B,A and B,D,A,B are longest common subsequences of X and

45、 Y(length=4)B,C,A,however is not a LCS of X and Y第56页/共158页57Brute-Force SolutionFor every subsequence of Xm,check whether its a subsequence of YnThere are 2m subsequences of Xm to checkEach subsequence takes(n)time to checkScan Yn for first letter,from there scan for second,and so onRunning time:(n

46、2m)第57页/共158页58NotationsGiven a sequence Xm=x1,x2,xm we define the i-th prefix of Xm,for i=0,1,2,mXi=x1,x2,xici,j=the length of a LCS of the sequences Xi=x1,x2,xi and Yj=y1,y2,yj第58页/共158页59Step 1:Optimal substructureTheorem(Optimal substructure of an LCS)Let Xm=and Yn=be sequences,and let Zk=be som

47、e LCS of Xm and Yn.1.If xm=yn,then zk=xm=yn and zk-1 is an LCS of Xm-1 and 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.第59页/共158页60Step 2:A recursive solutionCase 1:xi=yje.g.:Xi=A,B,D,EYj=Z,B,EAppend xi=yj to the LCS of Xi-1 and Yj

48、-1Must find a LCS of Xi-1 and Yj-1 optimal solution to a problem includes optimal solutions to subproblems第60页/共158页61A Recursive SolutionCase 2:xi yje.g.:Xi=A,B,D,GYj=Z,B,DMust solve two problemsfind a LCS of Xi-1 and Yj:Xi-1=A,B,D and Yj=Z,B,Dfind a LCS of Xi and Yj-1:Xi=A,B,D,G and Yj=Z,BOptimal

49、solution to a problem includes optimal solutions to subproblemsci,j=max ci-1,j,ci,j-1 第61页/共158页62Overlapping SubproblemsTo find a LCS of Xm and YnWe may need to find the LCS between Xm and Yn-1 and that of Xm-1 and YnBoth the above subproblems has the subproblem of finding the LCS of Xm-1 and Yn-1

50、Subproblems share subsubproblems第62页/共158页63Step 3:Computing the Length of the LCS0if i=0 or j=0ci,j=ci-1,j-1+1if xi=yjmax(ci,j-1,ci-1,j)if xi yj00000000000yj:xmy1y2ynx1x2xiji012nm120firstsecondci,j第63页/共158页64Additional Information 0 if i,j=0ci,j=ci-1,j-1+1 if xi=yj max(ci,j-1,ci-1,j)if xi yj000000