动态规划(矩阵连乘)详解.ppt

* 实验三 动态规划算法 ——矩阵连乘问题 * 动态规划的应用：矩阵连乘 例:A1A2相乘，设这2个矩阵的维数分别为10*5，5*3运算次数10*5*3=150。 问题：给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1，2…，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。 * 假设：给定n个矩阵 ， 其中 与 是可乘 的， 。考察这n个矩阵的连乘积 矩阵乘法满足结合律，计算矩阵的连乘可以有许多不同的计算次序，这种计算次序可以用加括号的方式来确定 若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积 动态规划的应用：矩阵连乘 * 完全加括号的矩阵连乘积可递归定义为： 单个矩阵是完全加括号的 矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=(BC) 矩阵连乘 * 16000, 10500, 36000, 87500, 34500 例如：表格中有四个矩阵及相应维数 总共有五种完全加括号的方式 矩阵连乘 矩阵 A B C D 维数 50×10 10×40 40×30 30×5 * 矩阵连乘问题 将矩阵连乘积 简记为A[i:j] ，这里i≤j 考察计算A[i:j]的最优计算次序。设这个计算次序在矩阵 Ak和Ak+1之间将矩阵链断开，i≤kj，则其相应完全 加括号方式为 计算量：A[i:k]的计算量加上A[k+1:j]的计算量，再加上 A[i:k]和A[k+1:j]相乘的计算量 * 2、建立递归关系 ①设计算A[i:j]，1≤i≤j≤n，所需要的最少数乘次数m[i][j]，则原问题的最优值为m[1][n] ②当i=j时，A[i:j]=Ai，因此，m[i][i]=0，i=1,2,…,n ③当ij时， ∴可以递归地定义m[i][j]为： 这里 的维数为 （断点）的位置只有 种可能 * 3、计算最优值 矩阵 A1 A2 A3 A4 A5 A6 数组p p0?p1 p1?p2 p2?p3 p3?p4 p4?p5 p5?p6 维数值 30?35 35?15 15?5 5?10 10?20 20?25 根据MatrixChain动态规划算法： ①计算次序（如图） * 3、计算最优值 矩阵 A1 A2 A3 A4 A5 A6 数组p p0?p1 p1?p2 p2?p3 p3?p4 p4?p5 p5?p6 维数值 30?35 35?15 15?5 5?10 10?20 20?25 根据MatrixChain动态规划算法： ②计算m[i][j]数乘次数 Ⅰ计算A1、A2、A3、A4、A5、A6 Ⅱ计算(A1A2)(A2A3)(A3A4)(A4A5)(A5A6) Ⅲ计算(A1A2A3)(A2A3A4)(A3A4A5)(A4A5A6) Ⅳ计算(A1A2A3A4)(A2A3A4A5)(A3A4A5A6) Ⅴ计算(A1A2A3A4A5)(A2A3A4A5A6) Ⅵ计算(A1A2A3A4A5A6) * 3、计算最优值 矩阵 A1 A2 A3 A4 A5 A6 数组p p0?p1 p1?p2 p2?p3 p3?p4 p4?p5 p5?p6 维数值 30?35 35?15 15?5 5?10 10?20 20?25 根据MatrixChain动态规划算法： ②计算m[i][j]数乘次数 m[2][5]=min m[2][2]+m[3][5]+p1p2p5=13000 m[2][3]+m[4][5]+p1p3p5=7125 m[2][4]+m[5][5]+p1p4p5=11375 最小值为7125，断点的位置为3 A2 (A3 A4 A5)中的两种情况： 1. A2(A3(A4A5)): m[2][5]=m[2][2]+m[3][3]+m[4][5]+p2p3p5+p1p2p5 2. A2 ((A3 A4) A5) m[2][5]=m[2][2]+m[3][4]+m[5][5]+p2p4p5+p1p2p5 (A2 A3)(A4 A5) (A2 A3A4) A5 * 3、计算最优值 矩阵 A1 A2 A3 A4 A5 A6 数组p p0?p1 p1?p2 p2?p3 p3?p4 p4?p5 p5?p6 维数值 30?35 35?15 15