算法设计-LEC8(3)

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

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新教学研究算法设计-LEC8(3)全文阅读和word下载服务。