算法设计-LEC8

华中科技大学管理学院算法设计课件,动态规划,“我为人人”服务队收集整理上传

动态规划(Dynamic Programming)算法设计与分析 Algorithms Design& Analysis第八讲：动态规划华中科技大学软件学院邱德红主讲 2005年4月 An algorithm design technique (like divide and conquer)(和分治法一样,是一种算法设计技术) Divide and conquer(分治法)– Partition the problem into independent subproblems (分割成独立的子问题)– Solve the subproblems recursively (递归解决子问题)– Combine the solutions to solve the original problem (合并求得初始问题的解)1

2

Dynamic Programming Applicable when subproblems are not independent (子问题非独立)– Subproblems share subsubproblems (子问题求解依赖其子问题的解)– A divide and conquer approach would repeatedly solve the common subproblems(分治法通过递归方式解决性质相同的子问题)– Dynamic programming solves every subproblem just once and stores the answer in a table (动态规划每次解决一个子问题，并将结果存储在表格中)

动态规划(Dynamic Programming) Used for optimization problems(适合优化问题)– A set of choices must be made to get an optimal solution (通过适当的选择来获得问题的最优解)– Find a solution with the optimal value (minimum or maximum) (找到具有最优解决方案及其最优值：装配线排程方案以及该方案的生产时间)– There may be many solutions that return the optimal value: an optimal solution (导致最优的解决方案可能不止一个)3 4

动态规划算法(Dynamic Programming Algorithm)1. Characterize the structure of an optimal solution (描述最优解的结构特征) 2. Recursively define the value of an optimal solution (定义最优解决方案的递归形式) 3. Compute the value of an optimal solution in a bottomup fashion(以自底向上的方式计算最优解决方案的值) 4. Construct an optimal solution from computed information (从计算信息构造出最优解决方案)

装配线排程问题 (Assembly Line Scheduling) Automobile factory with two assembly lines(汽车厂两条装配线)– Each line has n stations: S1,1, . . ., S1,n and S2,1, . . ., S2,n(每条装配线有n个工序站台)– Corresponding stations S1, j and S2, j perform the same function but can take different amounts of time a1, j and a2, j (每条装配线的第j个站台的功能相同,但是效率不一致)– Entry times e1 and e2 and exit times x1 and x2(上线和下线时间)

5

6

华中科技大学管理学院

华中科技大学管理学院算法设计课件,动态规划,“我为人人”服务队收集整理上传

装配线(Assembly Line) After going through a station, can either (在一个工序台 Si,j作业完成之后，汽车可以):– stay on same line at no cost, or(立即(时间为0)进入本装配线的下一工序台)– transfer to other line: cost after Si,j is ti,j, j= 1, . . ., n– 1(变换到另一装配线,耗时ti,j )

装配线排程(Assembly Line Scheduling) Problem: what stations should be chosen from line 1 and wh

ich from line 2 in order to minimize the total time through the factory for one car?(如何充分利用两条装配线,使得组装一辆汽车的时间最短?)

7

8

解决方法之一(One Solution) Brute force(蛮力法)– Enumerate all possibilities of selecting stations (计算装配线排程所有可能的组合情况)– Compute how long it takes in each case and choose the best one (比较并选择出最短时间的组合)

1.构建最优解(Structure of the Optimal Solution) Let’s consider all possible ways to get from the starting point through station S1,j (考虑所有从起点到达S1,j可能途径) Through S1, j - 1, then directly to S1, j (从S1, j - 1直接到S1, j ) Through S2, j - 1, then transfer over to S1, j (从S2, j - 1转换到S1, j ) S1,j-1 a1,j-1 t2,j-1 a2,j-19

– We have two choices of how to get to S1, j:(两种可能)

Problem:

1

2

3

4

n

1

0

0

1

1 1 if choosing line 1 at step j (= n)(反之标记为1)

0 if choosing line 2 at step j (= 3)第j步由第2条装配线执行，标记为0

S1,j a1,j

– There are 2n possible ways to choose stations(共有2n排程方法)– Infeasible when n is large(如果n很大,蛮力法计算将不可接受)

S2,j-1

10

1.构建最优解(Structure of the Optimal Solution) Suppose that the fastest way through S1, j is through S1, j– 1 (如果到达S1, j的最快装配路线来自S1, j– 1)– We must have taken a fastest way from entry through S1, j– 1(那么必须是从装配线起点经过S1, j– 1的最快装配路线)– If there were a faster way through S1, j - 1, we would use it instead(因为如果存在更快的经过S1, j - 1的装配路线，则可用之替换) Similarly for S2, j– 1(如果经过S1, j的最快装配路线来自S1, j– 1,同样分析)S1,j-1 S1,j a1,j-1 t2,j-1 a2,j-1 S2,j-111

最优化解的结构(Optimal Substructure) Generalization: an optimal solution to the problem find the fastest way through S1, j contains within it an optimal solution to subproblems: find the fastest way through S1, j - 1 or S2, j - 1.(寻求从起点到达S1, j最快装配路线，可分解为寻求从起点经过S1, j - 1 or S2, j - 1最快装配路线问题) This is referred to as the optimal substructure property(我们将这种具有分解递归特征的解的形式称为最优化结构特征) We use this property to construct an optimal solution to a problem from optimal solutions to subproblems(利用这种优化构造特征，从子问题的最优化解获得整个问题的最优化的解)

a1,j

12

华中科技大学管理学院

华中科技大学管理学院算法设计课件,动态规划,“我为人人”服务队收集整理上传

2.递归解(A Recursive Solution) Define the value of an optimal solution in terms of the optimal solution to subproblems(利用子问题的最优解，通过递归的方式求解原问题的最优解) Assembly line subproblems(装配线排程子问题)– Finding the fastest way through station j on both lines

, j= 1, 2,…, n (即是经过两条第j个工作台的最快线路问题， j= 1, 2,…, n )

2.递归解(A Recursive Solution) f*= the fastest time to get through the entire factory(问题最优解，完成所有装配过程的最短时间) fi[j]= the fastest time to get from the starting point through station Si,j(表示从起点经过Si,j工序的最短时间)f*= min (f1[n]+ x1, f2[n]+ x2)

13

14

2.递归解(A Recursive Solution) Compute fi[j] for j= 2, 3,…,n, and i= 1, 2(对于i= 1, 2和j= 2, 3,…,n,计算fi[j] ) Fastest way through S1, j is either:(经过S1, j的两种情况)– the way through S1, j - 1 then directly through S1, j, or(经过S1, j 1 ) f1[j - 1]+ a1,j

2.递归解(A Recursive Solution) fi[j]= the fastest time to get from the starting point through station Si,j (从起点经过Si,j工序的最短时间) j= 1 (getting through station 1)(经过工作台1的最短时间) f1[1]= e1+ a1,1 f2[1]= e2+ a2,1

– the way through S2, j - 1, transfer from line 2 to line 1, then S1,j-1 through S1, j (经过S2, j - 1 ) f2[j -1]+ t2,j-1+ a1,ja1,j-1 t2,j-1 f1[j]= min(f1[j - 1]+ a1,j,f2[j -1]+ t2,j-1+ a1,j) a2,j-1 S2,j-1

S1,j a1,j

15

16

2.递归解(A Recursive Solution)e1+ a1,1 min(f1[j - 1]+ a1,j,f2[j -1]+ t2,j-1+ a1,j) e2+ a2,1 if j= 1 if j≥ 2 if j= 1

3.计算最优解(Computing the Optimal Solution)f*= min (f1[n]+ x1, f2[n]+ x2)(自顶向下求最优解) f1[j]= min(f2[j - 1]+ a2,j,f1[j -1]+ t1,j-1+ a2,j)1 2 f1(2) f2(2) 3 f1(3) f2(3) 4 times 4 f1(4) f2(4) 2 times 5 f1(5) f2(5)

f1[j]=

f1[j] f2[j]

f1(1) f2(1)

f2[j]=

min(f2[j - 1]+ a2,j,f1[j -1]+ t1,j-1+ a2,j) if j≥ 2

Solving top-down would result in exponential running time (自顶向下导致指数增长的计算时间)17 18

华中科技大学管理学院

华中科技大学管理学院算法设计课件,动态规划,“我为人人”服务队收集整理上传

3.计算最优解(Computing the Optimal Solution) For j≥ 2, each value fi[j] depends only on the values of f1[j– 1] and f2[j - 1](对于j≥ 2,计算fi[j]与f1[j– 1]和f2[j - 1]的值相关) Compute the values of fi[j](如何计算fi[j]? )– in increasing order of j( j递增)1 2 3

4、构造最优方案(Construct the Optimal Solution) We need the sequence of what line has been used at each station (表示哪条装配线哪些工序台被利用的序列)– li[j]– the line number (1, 2) whose station (j - 1) has been used to get in fastest time through Si,j, j= 2, 3,…, n( li[j]表示经过Si,j的最优排程序列)

increasing j4 5

f1[j] f2[j] Bottom-up approach(自底向上的方法)– First find optimal solutions to subproblems(求解子问题的解)– Find an optimal solution to the problem from the subproblems(从子问题的解构造出原问题的最优解)19

– l* - the line whose station n is used to get in the fastest way through the entire fac

tory( l*表示整个排程问题的最优序列)

increasing j4

2

3

5

l1[j] l2[j]20

1. f1[1]← e1+ a1,1 3. for j← 2 to n 4. 5. 6. 7. 8. 9. 10. 11. 12.21

最优排程算法：FASTEST-WAY(a, t, e, x, n)Compute initial values of f1 and f2(初值计算)

2. f2[1]← e2+ a2,1

do if f1[j - 1]+ a1,j≤ f2[j - 1]+ t2, j-1+ a1, j then f1[j]← f1[j - 1]+ a1, j l1[j]← 1 else f1[j]← f2[j - 1]+ t2, j-1+ a1, j l1[j]← 2 if f2[j - 1]+ a2, j≤ f1[j - 1]+ t1, j-1+ a2, j then f2[j]← f2[j - 1]+ a2, j l2[j]← 2 else f2[j]← f1[j - 1]+ t1, j-1+ a2, j l2[j]← 1Compute the values of f2[j] and l2[j] Compute the values of f1[j] and l1[j]

e1+ a1,1, f1[j]= min(f1[j - 1]+ a1,j,f2[j -1]+ t2,j-1+ a1,j)1 2 3 4 5

if j= 1 if j≥ 2

f1[j] f2[j]

9 12

18[1] 16[1]

20[2] 22[2]

24[1] 25[1]

32[1] 30[2]

f*=

35[1]

13.

22

FASTEST-WAY(a, t, e, x, n) (cont.)14. if f1[n]+ x1≤ f2[n]+ x2 15. 16. 17. 18. then f*= f1[n]+ x1 l*= 1 else f*= f2[n]+ x2 l*= 2Compute the values of the fastest time through the entire factory(最终的最优解)

4.构造最优的排程方案(Construct an Optimal Solution) Alg.: PRINT-STATIONS(l, n) i← l* print“line” i“, station” n for j← n downto 2 do i←li[j] print“line” i“, station” j - 11 2 3 4 5

line 1, station 5 line 1, station 4 line 1, station 3 line 2, station 2 line 1, station 1

f1[j]/l1[j] f2[j]/l2[j]23

9 12

18[1] 16[1]

20[2] 22[2]

24[1] 25[1]

32[1] 30[2]

l*= 1

24

华中科技大学管理学院

华中科技大学管理学院算法设计课件,动态规划,“我为人人”服务队收集整理上传

动态规划算法(Dynamic Programming Algorithm)1.–

矩阵链相乘(Matrix-Chain Multiplication)Problem: given a sequence A1, A2,…, An , compute the product:(问题：给定矩阵序列A1, A2,…, An,求它们的积) A1 A2 An Matrix compatibility:(矩阵相乘的条件) C=A B colA= rowB rowC= rowA colC= colB A1 A2 Ai Ai+1 An coli= rowi+126

Characterize the structure of an optimal solution(最优解的结构特征)Fastest time through a station depends on the fastest time on previous stations (比如，通过某个工作台的最快路线与通过前一工作台的最快路线相关)

2.– 3.–

Recursively define the value of an optimal solution(递归表示) f1[j]= min(f1[j - 1]+ a1,j,f2[j -1]+ t2,j-1+ a1,j) Compute the value of an optimal solution in a bottom-up fashion(计算最优值，自底向上)Fill in the fastest time table in increasing order of j (station#)

4.–

Construct an optimal solution from computed information(构造导致最优解的最佳方案，依赖求解过程的某些计算信息)Use an additional table to help reconstruct the optimal solution

25

矩阵链相乘(Matrix-Chain Multiplication) In what order should we multiply the matrices?(矩阵链相乘将按照什么顺序进行?) A1 A2 An Parenthesize the product to get the

order in which matrices are multiplied(用括号表示出矩阵链相乘的顺序) E.g.: A1 A2 A3= ((A1 A2) A3)= (A1 (A2 A3)) Which one of these orderings should we choose?(那种顺序最优?)– The order in which we multiply the matrices has a significant impact on the cost of evaluating the product(矩阵链相乘的顺序极大的影响计算的代价)

矩阵相乘:MATRIX-MULTIPLY(A, B)if columns[A]≠ rows[B] then error“incompatible dimensions” else for i← 1 to rows[A] do for j← 1 to columns[B] rows[A] cols[A] cols[B] multiplications do C[i, j]= 0 for k← 1 to columns[A] do C[i, j]← C[i, j]+ A[i, k] B[k, j] kj i rows[A] A cols[B]= i B rows[A] C28

j

cols[B]

*

k

27

矩阵链相乘示例(Example)A1 A2 A3 A1: 10 x 100 A2: 100 x 5 A3: 5 x 50 1. ((A1 A2) A3): A1 A2= 10 x 100 x 5= 5,000 (10 x 5) ((A1 A2) A3)= 10 x 5 x 50= 2,500 Total: 7,500 scalar multiplications 2. (A1 (A2 A3)): A2 A3= 100 x 5 x 50= 25,000 (100 x 50) (A1 (A2 A3))= 10 x 100 x 50= 50,000 Total: 75,000 scalar multiplications one order of magnitude difference!!(数量级区别)29

矩阵链相乘(Matrix-Chain Multiplication) Given a chain of matrices A1, A2,…, An , where for i= 1, 2,…, n matrix Ai has dimensions pi-1x pi, fully parenthesize the product A1 A2 An in a way that minimizes the number of scalar multiplications.(如何决定矩阵链相乘的顺序，即如何放置括号，使矩阵链相乘所需要的数量乘法的次数最小) A1 p0 x p 1

A2

Ai

Ai+1pi x pi+1

An

p1 x p2

pi-1 x pi

pn-1 x pn

30

华中科技大学管理学院

华中科技大学管理学院算法设计课件,动态规划,“我为人人”服务队收集整理上传

蛮力法(Brute Force) Brute force: check all possible orders?(逐一比较)– P(n): number of ways to multiply n matrices. (n长度矩阵链相乘的可能方法)

1.最优矩阵链相乘顺序结构(The Structure of an Optimal Parenthesization) Notation:(标记Ai…j ) Ai…j= Ai Ai+1 Aj, i≤ j For i< j: Ai…j= Ai Ai+1 Aj= Ai Ai+1 Ak Ak+1 Aj= Ai…k Ak+1…j Suppose that an optimal parenthesization of Ai…j splits the i≤ k< j(假设矩阵 product between Ak and Ak+1, where链Ai…j相乘的最优顺序在Ak和Ak+1分割,即)31 32

–

, exponential in n.

Any efficient solution? Dynamic programming! (高效率方法)

Optimal SubstructureAi…j= Ai…k Ak+1…j The parenthesization of the“prefix” Ai…k must be an optimal parenthesization(则Ai…k必须是具有最优相乘顺序的矩阵链) If there were a less costly way to parenthesize Ai…k, we could substitute that one in the parenthesization of Ai…j and produce a parenthesization with a lower cost than the optimum contradiction!(否则,可以用更优顺序取代， Ak+1…j同样) An optimal solution to an instance of the matrix-chain multiplication contains within it

optimal solutions to

2.递归解(A Recursive Solution) Subproblem: determine the minimum cost of parenthesizing (求Ai…j数量乘法的次数最小的运算顺序) Ai…j= Ai Ai+1 Aj for 1≤ i≤ j≤ n

Let m[i, j]= the minimum number of multiplications needed to compute Ai…j (利用m[i, j]标记Ai…j最小的数量乘法次数)– Full problem (A1..n): m[1, n]33

subproblems(这样,就将原矩阵链Ai…j最优相乘顺序问题转变为子矩阵序列Ai…k、Ak+1…j的最优相乘顺序问题)

– i= j: Ai…i= Ai m[i, i]= 0, for i= 1, 2,…, n

34

2.递归解(A Recursive Solution) Consider the subproblem of parenthesizing(矩阵链Ai…j相乘在Ak和Ak+1分割) Ai…j= Ai Ai+1 Aj= Ai…k Ak+1…jm[i, k]

2. A Recursive Solution (cont.)m[i, j]= m[i, k]+ m[k+1, j]+ pi-1pkpj We do not know the value of k(如何确定k?k有j– i个选择情况)– There are j– i possible values for k: k= i, i+1,…, j-1 Minimizing the cost of parenthesizing the product Aj becomes:(最小数量乘法次数为:) Ai Ai+1

for 1≤ i≤ j≤ npi-1pkpj

for i≤ k< j

m[k+1,j]

Assume that the optimal parenthesization splits the product Ai Ai+1 Aj at k (i≤ k< j)(在Ak和Ak+1分割如果是最优计算顺序) m[i, j]=

0 if i= j m[i, j]= min{m[i, k]+ m[k+1, j]+ pi-1pkpj} if i< ji≤k<j

m[i, k]

+

m[k+1, j]

+

pi-1pkpj

min# of multiplications to compute Ai…k

min# of multiplications# of multiplications to compute Ak+1…j to compute Ai…kAk…j35 36

华中科技大学管理学院

华中科技大学管理学院算法设计课件,动态规划,“我为人人”服务队收集整理上传

矩阵链相乘(Matrix-Chain Multiplication)– m[1, n]: the cheapest cost to compute A1..n.

自底向上动态规划矩阵链相乘最优顺序算法 (Bottom-Up DP Matrix-Chain Order)Matrix-Chain-Order(p) 1. n← length[p]-1; 2. for i← 1 to n 3. m[i, i]← 0; 4. for l← 2 to n 5. for i← 1 to n– l+1 6. j← i+ l -1; 7. m[i, j]←∞; 8. for k← i to j -1 9. q← m[i, k]+ m[k+1, j]+ pI-1pkpj; 10. if q< m[i, j] 11. m[i, j]← q; 12. s[i, j]← k; 13. return m and s

Applicability of dynamic programming(动态规划的适用性)– Optimal substructure: an optimal solution contains within it optimal solutions to subproblems.(优化子结构)– Overlapping subproblem: a recursive algorithm revisits the same problem over and over again; onlyθ(n2) subproblems.(迭代的解)37

38

构造最优相乘顺序(Constructing an Optimal Solution) s[i, j]: value of k such that the optimal parenthesization of Ai Ai+1… Aj splits between Ak and Ak+1.(s[i, j]:记录了Ai Ai+1… Aj的最优分割顺序位置) Optimal matrix A1..n multiplication: A1..s[1, n]As[1, n]+ 1..n. Exp: call Matrix-Chain-Multiply(A, s, 1, 6): ((A1 (A2 A3))((A4 A5) A6)).Matrix-Chain-Multiply(A, s, i, j) 1. if j> i 2. X← Matrix-Chain-Multiply(A, s, i, s[i, j]); 3. Y← Matrix-Chain-Multiply(A, s, s[i, j]+1, j); 4. return Matrix-M

ultiply(X, Y); 5. else return Ai;

最长共同子序列(Longest Common Subsequence)The sequence Z= (B, C, A) is a subsequence of X= (A, B, C, B, D, A, B). (子序列的概念) It is also a subsequence of Y= (B, D, C, A, B, A). It is a common subsequence of X and Y. (共同子序列) It is not a longest common subsequence (最长共同子序列) because Z′= (B, D, A, B) is a longer common subsequence.39

最长共同子序列例 Exp: X=<a, b, c, b, d, a, b> and Y=<b, d, c, a, b, a> LCS=<b, c, b, a> (also, LCS=<b, d, a, b>). Exp: DNA sequencing:– S1= ACCGGTCGAGATGCAG;– S2= GTCGTTCGGAATGCAT; LCS S3= GTCGGATGCA

蛮力法求LCS Brute-force method:– Enumerate all subsequences of X and check if they appear in Y.(穷举X的所有子序列，检查其是否在Y中出现，然后选出LCS)– X= (x1, x2,…, xm)有2m个子序列。

41

42

华中科技大学管理学院

华中科技大学管理学院算法设计课件,动态规划,“我为人人”服务队收集整理上传

LCS的最优结构(Optimal Substructure of LCS)Given two sequences X= (x1, x2,…, xm) and Y= (y1, y2,…, yn) and an LCS Z= (z1, z2,…, zk) of X and Y.(给定两个序列X= (x1, x2,…, xm)和Y= (y1, y2,…, yn)他们的LCS Z= (z1, z2,…, zk) ) If xm= yn, then zk= xm andZk– 1 is an LCS of Xm– 1 and Yn– 1. (如果xm= yn,则有zk= xm,和 Zk– 1是Xm– 1和Yn– 1的LCS) If xm≠ yn, then zk≠ xm implies Z is an LCS of Xm– 1 and Y. (如果xm≠ yn,则 zk≠ xm意味Z是Xm– 1和Y的LCS) If xm≠ yn, then zk≠ yn implies Z is an LCS of X and Yn– 1. (如果xm≠ yn,则 zk≠ yn意味Z是X和Yn– 1的LCS)

LCS递归解(A Recursive Formulation of LCS)

C= length of LCS of X and Y.(C: X和Y最长共同子序列的长度) c(i, j)= length of LCS of Xi and Yj; ( c(i, j):Xi和 Yj最长共同子序列的长度) that is, C= c(m, n).

LCS算法 To compute c[i, j], we need c[i-1, j-1], c[i-1, j], and c[i, j-1]. b[i, j]: points to the table entry w.r.t. the optimal subproblem solution chosen when computing c[i, j]. ( b[i, j]:记录求解过程信息) LCS-Length(X,Y)1. m← length[X]; 2. n← length[Y]; 3. for i← 1 to m 4. c[i, 0]← 0; 5. for j← 0 to n 6. c[0, j]← 0; 7. for i← 1 to m 8. for j← 1 to n 9. if xi= yj 10. c[i, j]← c[i-1, j-1]+1 11. b[i, j]←“⊥” 12. else if c[i-1,j]≥ c[i, j-1] 13. c[i,j]← c[i-1, j] 14. b[i, j]←``↑ '' 15. else c[i, j]← c[i, j-1] 16. b[i, j]←“←“ 17. return c and b

算法分析 it simply fills in the table.(填表) Computing one table entry costs O(1) time.(一个格子的计算量) There are n· m table entries.( n· m个格子) The cost of the algorithm is O(nm).(总计算开销)

45

华中科技大学管理学院

本文来源：https://www.bwwdw.com/article/qkoj.html