算法导论——动态规划算法Dynamic Programming_357209964

1、Dynamic ProgrammingBin WangSchool of SoftwareTsinghua UniversityOctober 15, 2010Assembly-line schedulingMatrix-chain multiplicationElements of DMLCSOptimal binary search treesOutline1Assembly-line scheduling2Matrix-chain multiplication3Elements of DM4LCS5Optimal binary search treesAssembly-line sche

2、dulingMatrix-chain multiplicationElements of DMLCSOptimal binary search treesOverviewDynamic Programming vs Divide & Conquer1 Samenesspartition the problem into subproblems combining the solutions from subproblems2 Differencesoverlapping subproblems vs no overlapping subproblemsDynamic programming i

3、s typically applied to optimization problems.3/ 98Assembly-line schedulingMatrix-chain multiplicationElements of DMLCSOptimal binary search treesOverviewDynamic Programming vs Divide & Conquer1 Samenesspartition the problem into subproblems combining the solutions from subproblems2 Differencesoverla

4、pping subproblems vs no overlapping subproblemsDynamic programming is typically applied to optimization problems.4/ 98Assembly-line schedulingMatrix-chain multiplicationElements of DMLCSOptimal binary search treesOverviewSteps of Dynamic Programming1234Characterize the structure of an optimal soluti

5、on.Recursively define the value of an optimal solution.Compute the value of an optimal solution in a bottom-up fashion.Construct an optimal solution from computed information.5/ 98Assembly-line schedulingMatrix-chain multiplicationElements of DMLCSOptimal binary search treesOverviewSteps of Dynamic

6、Programming1234Characterize the structure of an optimal solution.Recursively define the value of an optimal solution.Compute the value of an optimal solution in a bottom-up fashion.Construct an optimal solution from computed information.6/ 98Assembly-line schedulingMatrix-chain multiplicationElement

7、s of DMLCSOptimal binary search treesOverviewSteps of Dynamic Programming1234Characterize the structure of an optimal solution.Recursively define the value of an optimal solution.Compute the value of an optimal solution in a bottom-up fashion.Construct an optimal solution from computed information.7

8、/ 98Assembly-line schedulingMatrix-chain multiplicationElements of DMLCSOptimal binary search treesOverviewSteps of Dynamic Programming1234Characterize the structure of an optimal solution.Recursively define the value of an optimal solution.Compute the value of an optimal solution in a bottom-up fas

9、hion.Construct an optimal solution from computed information.8/ 98Assembly-line schedulingMatrix-chain multiplicationElements of DMLCSOptimal binary search treesTo find the fastest way through a factoryLine 1e1enterse2Line 2S1,1S1,2S1,3S1,4S1,nS1,na1,1a1,2a1,3a1,4a1,na1,nx1t1,1t1,2t1,3t1,nexitst2,1t

10、2,2t2,3t2,nx2a2,1a2,2a2,3a2,4a2,na2,nS2,1S2,2S2,3S2,4S2,nS2,nBrute forceThere are 2n possible ways to choose stations, so it will cost (2n) time.9/ 98Assembly-line schedulingMatrix-chain multiplicationElements of DMLCSOptimal binary search treesTo find the fastest way through a factoryLine 1e1enters

11、e2Line 2S1,1S1,2S1,3S1,4S1,nS1,na1,1a1,2a1,3a1,4a1,na1,nx1t1,1t1,2t1,3t1,nexitst2,1t2,2t2,3t2,nx2a2,1a2,2a2,3a2,4a2,na2,nS2,1S2,2S2,3S2,4S2,nS2,nBrute forceThere are 2n possible ways to choose stations, so it will cost (2n) time.10/ 98Assembly-line schedulingMatrix-chain multiplicationElements of DM

12、LCSOptimal binary search treesSteps of DM for Assembly-line schedulingStep1: The structure of the fastest way12The fastest way through station S1,j is eitherThe fastest way through station S1 j 1 or,The fastest way through station S2 j 1.,Symmetrically, fastest way through station S2,j is eitherThe

13、fastest way through station S2 j 1 or,The fastest way through station S1 j 1.,11/ 98Assembly-line schedulingMatrix-chain multiplicationElements of DMLCSOptimal binary search treesSteps of DM for Assembly-line schedulingStep2: A recursive solutionLet fi j denote the fastest possible time through stat

14、ion Si,j .f = min(f1n + x1, f2n + x2)12/ 98Assembly-line schedulingMatrix-chain multiplicationElements of DMLCSOptimal binary search treesSteps of DM for Assembly-line schedulingStep2: A recursive solutionLet fi j denote the fastest possible time through station Si,j .f = min(f1n + x1, f2n + x2)e1 +

15、 a1,1f1j =min(f1j 1 + a1,j ,f2j 1 + t2,j1 + a1,j )j = 1,j 2.13/ 98Assembly-line schedulingMatrix-chain multiplicationElements of DMLCSOptimal binary search treesSteps of DM for Assembly-line schedulingStep2: A recursive solutione2 + a2,1j = 1,f2j =min(f2j 1 + a2,j ,f1j 1 + t1,j1 + a2,j ) j 2.14/ 98A

16、ssembly-line schedulingMatrix-chain multiplicationElements of DMLCSOptimal binary search treesSteps of DM for Assembly-line schedulingFASTEST-WAY (a, t , e, x , n)1 f11 e1 + a1,12 f21 e2 + a2,13 for j 2 to n4 do if f1j 1 + a1,j f2j 1 + t2,j 1 + a1,j5then f1j f1j 1 + a1,j6else f1j f2j 1 + t2,j 1+ a1,

17、j7if f2j 1 + a2,j f1j 1 + t1,j 1 + a2,j8then f2j f2j 1 + a2,j9else f2j f1j 1 + t1,j 1+ a2,j10 if f1n + x1 f2n + x211 then f = f1n + x112 else f = f2n + x2Step3: Computing the fastest times15/ 98Assembly-line schedulingMatrix-chain multiplicationElements of DMLCSOptimal binary search treesSteps of DM

18、 for Assembly-line schedulingFASTEST-WAY (a, t , e, x , n)1 f11 e1 + a1,12 f21 e2 + a2,13 for j 2 to n4 do if f1j 1 + a1,j f2j 1 + t2,j 1 + a1,j5then f1j f1j 1 + a1,j ,l1j 16else f1j f2j 1 + t2,j 1 + a1,j , l1j 27if f2j 1 + a2,j f1j 1 + t1,j 1 + a2,j8then f2j f2j 1 + a2,j ,l2j 29else f2j f1j 1 + t1,

19、j 1 + a2,j , l2j 110 if f1n + x1 f2n + x211 then f = f1n + x1, l = 112 else f = f2n + x2, l = 2Step3: Computing the fastest times16/ 98Assembly-line schedulingMatrix-chain multiplicationElements of DMLCSOptimal binary search treesAn instance of assembly-line problemS1,1S1,2S1,3S1,4S1,5S1,6Line 17932

20、231enters2124Line 28 5 6S2,1S2,2S2,3j123456f1j91820243235f = 38f2j1216222530374 8 4334exits2124 5 7S2,4S2,5S2,6j23456l1j12112l = 1l2j1212217/ 98Assembly-line schedulingMatrix-chain multiplicationElements of DMLCSOptimal binary search treesSteps of DM for Assembly-line schedulingStep4: Constructing t

21、he fastest wayPRINT-STATIONS(l , n)1 i l 2 print “line” i “, station” n3 for j n downto 24 do i li j 5print “line” i “, station” j 118/ 98Assembly-line schedulingMatrix-chain multiplicationElements of DMLCSOptimal binary search treesSteps of DM for Assembly-line schedulingStep4: Constructing the fas

22、test wayline 1, station 6line 2, station 4line 2, station 2line 2, station 5 line 1, station 3 line 1, station 119/ 98Assembly-line schedulingMatrix-chain multiplicationElements of DMLCSOptimal binary search treesOverviewPurposeGive a sequence A1, A2, . . . , An of n matrices to be multiplied, and w

23、e wish to compute the product: A1A2 . . . An.Fully parenthesizedA product of matrices is fully parenthesized if it is either a single matrix or the product of two fully parenthesized matrix products, surrounded by parentheses.20/ 98Assembly-line schedulingMatrix-chain multiplicationElements of DMLCS

24、Optimal binary search treesOverviewPurposeGive a sequence A1, A2, . . . , An of n matrices to be multiplied, and we wish to compute the product: A1A2 . . . An.Fully parenthesizedA product of matrices is fully parenthesized if it is either a single matrix or the product of two fully parenthesized mat

25、rix products, surrounded by parentheses.21/ 98Assembly-line schedulingMatrix-chain multiplicationElements of DMLCSOptimal binary search treesOverviewExample(A1(A2(A3A4), (A1(A2A3)A4), (A1A2)(A3A4), (A1(A2A3)A4), (A1A2)A3)A4).22/ 98Assembly-line schedulingMatrix-chain multiplicationElements of DMLCSO

26、ptimal binary search treesOverviewMATRIX-MULTIPLY(A, B)1 if columnsA = rowsB2 then error “incompatible dimensions”3 else for i 1 to rowsA4do j 1 to columnsB5do Ci , j 06for k 1 to columnsA7do Ci , j Ci , j +Ai , k Bk , j 8return C23/ 98Assembly-line schedulingMatrix-chain multiplicationElements of D

27、MLCSOptimal binary search treesOverviewWhy parenthesized?Different costs incurred by different parenthesizations!ExampleA10100B1005C550A10100(B1005C550) :10 100 50 + 100 5 50 = 75, 000(A10100B1005)C550 :10 100 5 + 10 5 50 = 7, 50024/ 98Assembly-line schedulingMatrix-chain multiplicationElements of D

28、MLCSOptimal binary search treesOverviewWhy parenthesized?Different costs incurred by different parenthesizations!ExampleA10100B1005C550A10100(B1005C550) :10 100 50 + 100 5 50 = 75, 000(A10100B1005)C550 :10 100 5 + 10 5 50 = 7, 50025/ 98Assembly-line schedulingMatrix-chain multiplicationElements of D

29、MLCSOptimal binary search treesBrute forceCounting the number of parenthesizationDenote the number of alternative parenthesizations of a sequence of n matrices by P(n), then:1P(n) =n1P P(k )P(n k )k =1P(n) grows as (4n/n 3 ).2n = 1,n 2.26/ 98Assembly-line schedulingMatrix-chain multiplicationElement

30、s of DMLCSOptimal binary search treesBrute forceCounting the number of parenthesizationDenote the number of alternative parenthesizations of a sequence of n matrices by P(n), then:1P(n) =n1P P(k )P(n k )k =1P(n) grows as (4n/n 3 ).2n = 1,n 2.27/ 98Assembly-line schedulingMatrix-chain multiplicationE

31、lements of DMLCSOptimal binary search treesStep1: The structure of an optimal parenthesizationSuppose that an optimal parenzhesization of Ai Ai+1 . . . A j split the product between Ak and Ak +1.Then the parenthesization of “prefix” subchain Ai Ai+1 . . . Ak within this optimal parenthesization of A

32、i Ai+1 . . . Aj must be an optimal parenthesization of Ai Ai+1 . . . Ak . Similarly, subchain Ak +1Ak +2 . . . Aj in the optimal parenthesization of must be an optimal parenthesization of Ak +1Ak + 2 . . . Aj .28/ 98Assembly-line schedulingMatrix-chain multiplicationElements of DMLCSOptimal binary s

33、earch treesStep1: The structure of an optimal parenthesizationSuppose that an optimal parenzhesization of Ai Ai+1 . . . A j split the product between Ak and Ak +1.Then the parenthesization of “prefix” subchain Ai Ai+1 . . . Ak within this optimal parenthesization of Ai Ai+1 . . . Aj must be an optim

34、al parenthesization of Ai Ai+1 . . . Ak . Similarly, subchain Ak +1Ak +2 . . . Aj in the optimal parenthesization of must be an optimal parenthesization of Ak +1Ak + 2 . . . Aj .29/ 98Assembly-line schedulingMatrix-chain multiplicationElements of DMLCSOptimal binary search treesStep1: The structure

35、of an optimal parenthesizationSuppose that an optimal parenzhesization of Ai Ai+1 . . . A j split the product between Ak and Ak +1.Then the parenthesization of “prefix” subchain Ai Ai+1 . . . Ak within this optimal parenthesization of Ai Ai+1 . . . Aj must be an optimal parenthesization of Ai Ai+1 .

36、 . . Ak . Similarly, subchain Ak +1Ak +2 . . . Aj in the optimal parenthesization of must be an optimal parenthesization of Ak +1Ak + 2 . . . Aj .30/ 98Assembly-line schedulingMatrix-chain multiplicationElements of DMLCSOptimal binary search treesStep2: A recursive solutionLet mi , j be the minimum

37、number of scalar multiplications needed to computer the matrix Ai.j ; for the full problem, a cheapest way would thus be m1, nLet us assume that the optimal parenthesization splits the productAi Ai+1 . . . Aj between Ak and Ak +1, wherei k j .31/ 98Assembly-line schedulingMatrix-chain multiplication

38、Elements of DMLCSOptimal binary search treesStep2: A recursive solutionLet mi , j be the minimum number of scalar multiplications needed to computer the matrix Ai.j ; for the full problem, a cheapest way would thus be m1, nLet us assume that the optimal parenthesization splits the productAi Ai+1 . .

39、 . Aj between Ak and Ak +1, wherei k j .32/ 98Assembly-line schedulingMatrix-chain multiplicationElements of DMLCSOptimal binary search treesStep2: A recursive solution0if i = j ,mi , j =min mi , k + mk + 1, j if i j .ik j+pi1pk pj 33/ 98Assembly-line schedulingMatrix-chain multiplicationElements of

40、 DMLCSOptimal binary search treesStep3: Computing the optimal costsMATRIX-CHAIN-ORDER (p)1 n lengthp 12 for i 1 to n3 do mi , i 04 for l 2 to n l is the chain length.5 do for i 1 to n l + 16do j i + l 17mi , j 8for k i to j 19do q mi , k + mk + 1, j + pi 1pk pj10if q mi , j 11then mi , j q12si , j k

41、13 return m and s34/ 98Assembly-line schedulingMatrix-chain multiplicationElements of DMLCSOptimal binary search treesStep3: Computing the optimal costsms6161515, 1252532j411, 87510, 5003ij4333i39, 3757, 1255, 37543333427, 8754, 3752, 5003, 5005213355115, 7502, 6257501, 0005, 000612345000000A1A2A3A4

42、A5A6matrixdimensionA130 35A235 15A315 5A45 10A510 20A620 2535/ 98Assembly-line schedulingMatrix-chain multiplicationElements of DMLCSOptimal binary search treesStep3: Computing the optimal costsms6161515, 1252532j411, 87510, 5003ij4333i39, 3757, 1255, 37543333427, 8754, 3752, 500 3, 5005213355115, 7

43、50 2, 6257501, 0005, 000612345000000A1A2A3A4A5A6m2, 2 + m3, 5 + p1p2p5= 13000= 0 + 2500 + 35 15 20m2, 3 + m4, 5 + p1p3p5m2, 5 = min= 7125= 2625 + 1000 + 35 5 20m2, 4 + m5, 5 + p1p4p5= 11375= 4375 + 0 + 35 10 2036/ 98Assembly-line schedulingMatrix-chain multiplicationElements of DMLCSOptimal binary s

44、earch treesConstructing an optimal solutionPRINT-OPTIMAL-PARENS(s, i , j )1 if i = j2 then print “A”i3 else print “(”PRINT-OPTIMAL-PARENS(s, i , si , j )PRINT-OPTIMAL-PARENS(s, si , j + 1, j )print “)”Example result(A1(A2A3)(A4A5)A6)37/ 98Assembly-line schedulingMatrix-chain multiplicationElements o

45、f DMLCSOptimal binary search treesConstructing an optimal solutionPRINT-OPTIMAL-PARENS(s, i , j )1 if i = j2 then print “A”i3 else print “(”PRINT-OPTIMAL-PARENS(s, i , si , j )PRINT-OPTIMAL-PARENS(s, si , j + 1, j )print “)”Example result(A1(A2A3)(A4A5)A6)38/ 98Assembly-line schedulingMatrix-chain multiplicationElements of DMLCSOptimal binary search treesHistoryIn 1973, S.Godbole presented the O(n3)algorithm.In 1975, A. K. Chandra from IBM