动态规划 (矩阵连乘)

1、1实验三实验三 动态规划算法动态规划算法矩阵连乘问题2动态规划的应用动态规划的应用：矩阵连乘矩阵连乘例例:A1A2相乘，设这相乘，设这2个矩阵的维数分别为个矩阵的维数分别为10*5，5*3运运算次数算次数10*5*3=150。问题：问题：给定给定n个矩阵个矩阵A1,A2,An，其中，其中Ai与与Ai+1是可乘的，是可乘的，i=1，2，n-1。如何确定计算矩阵连乘积的。如何确定计算矩阵连乘积的计算次序计算次序，使得依此次序计算矩阵，使得依此次序计算矩阵连乘积需要的连乘积需要的数乘次数数乘次数最少。最少。3假设：假设：给定给定n n个矩阵个矩阵 ， 其中其中 与与 是是可乘可乘 的，的， 。考察这

2、。考察这n n个矩阵的连乘积个矩阵的连乘积 n矩阵乘法满足矩阵乘法满足结合律结合律，计算矩阵的连乘可以有许多不同的计，计算矩阵的连乘可以有许多不同的计算次序，这种计算次序可以用算次序，这种计算次序可以用加括号加括号的方式来确定的方式来确定n若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用完全加括号，则可以依此次序反复调用2 2个矩阵相乘的标准算个矩阵相乘的标准算法计算出矩阵连乘积法计算出矩阵连乘积,.,21nAAAiA1iA1,.,2 , 1ninAAA.21动态规划的应用动态规划的应用：矩阵连乘矩阵

3、连乘4u完全加括号的矩阵连乘积可完全加括号的矩阵连乘积可递归递归定义为：定义为：单个单个矩阵是完全加括号的矩阵是完全加括号的矩阵连乘积矩阵连乘积A是完全加括号的，则是完全加括号的，则A可表示为可表示为2个完个完全加括号的矩阵连乘积全加括号的矩阵连乘积B和和C的乘积并加括号，即的乘积并加括号，即A=(BC)矩阵连乘矩阵连乘5)(DBCA)(DCAB)(DBCA)(CDBA)(CDAB16000, 10500, 36000, 87500, 34500例如：表格中有四个矩阵及相应维数例如：表格中有四个矩阵及相应维数u总共有五种完全加括号的方式总共有五种完全加括号的方式矩阵连乘矩阵连乘矩阵ABCD维数

4、501010404030 3056矩阵连乘问题矩阵连乘问题将矩阵连乘积将矩阵连乘积 简记为简记为Ai:j ，这里，这里ij jiiAAA.1考察计算考察计算Ai:j的最优计算次序。设这个计算次序在矩阵的最优计算次序。设这个计算次序在矩阵Ak和和Ak+1之间将矩阵链断开，之间将矩阵链断开，ikj，则其相应完全，则其相应完全加括号方式为加括号方式为).)(.(211jkkkiiAAAAAA计算量：计算量：Ai:k的计算量的计算量加上加上Ak+1:j的计算量的计算量，再加上，再加上Ai:k和和Ak+1:j相乘的计算量相乘的计算量7设计算Ai:j，1ijn，所需要的最少数乘次数mij，则原问题的最优值

5、为m1n 当i=j时，Ai:j=Ai，因此，mii=0，i=1,2,n当ij时，可以递归地定义mij为：jkipppjkmkimjim11这里 的维数为 iAiipp1jipppjkmkimjijimjki1min01jki （断点）的位置只有 种可能kij 8矩阵A1A2A3A4A5A6数组pp0p1p1p2p2p3p3p4p4p5p5p6维数值3035351515551010202025根据MatrixChain动态规划算法：计算次序（如图）9矩阵A1A2A3A4A5A6数组pp0p1p1p2p2p3p3p4p4p5p5p6维数值3035351515551010202025根据Matrix

6、Chain动态规划算法：计算mij数乘次数计算A1、A2、A3、A4、A5、A6计算(A1A2)(A2A3)(A3A4)(A4A5)(A5A6)计算(A1A2A3)(A2A3A4)(A3A4A5)(A4A5A6)计算(A1A2A3A4)(A2A3A4A5)(A3A4A5A6)计算(A1A2A3A4A5)(A2A3A4A5A6)计算(A1A2A3A4A5A6)10矩阵A1A2A3A4A5A6数组pp0p1p1p2p2p3p3p4p4p5p5p6维数值3035351515551010202025根据MatrixChain动态规划算法：计算mij数乘次数m25=min m22+m35+p1p2p5=

7、13000 m23+m45+p1p3p5=7125 m24+m55+p1p4p5=11375 最小值为最小值为7125，断点的位置为，断点的位置为3jipppjkmkimjijimjki1min01jkiA2 (A3 A4 A5)中的两种情况：1. A2(A3(A4A5):m25=m22+m33+m45+p2p3p5+p1p2p5 2. A2 (A3 A4) A5)m25=m22+m34+m55+p2p4p5+p1p2p5(A2 A3)(A4 A5)(A2 A3A4) A511矩阵A1A2A3A4A5A6数组pp0p1p1p2p2p3p3p4p4p5p5p6维数值303535151555101

8、0202025根据根据MatrixChain动态规划算法：动态规划算法：计算计算sij（断点（断点K的位置）的位置）m25=min m22+m35+p1p2p5=13000 m23+m45+p1p3p5=7125 m24+m55+p1p4p5=11375 最小值为最小值为7125，断点的位置为，断点的位置为312int MatrixChain:MChain() /求求A0:n-1的最优解值的最优解值 for (int i=0;in; i+) mii=0; for (int r=2; r=n; r+) for (int i=0; i=n-r; i+) int j=i+r-1; mij=mi+1j+pi*pi+1*pj+1; /mij 的初值的初值 sij=i; for (int k=i+1; kj; k+) int t=mik+mk+1j+pi*pk+1*pj+1;if (tmij) mij=t; sij=k; return m0n-1;13void MatrixChain:Traceback(int i, int j)if(i=j) coutAi; return;if (isij) cout(; Traceback(i, sij); i