第3章-动态规划-实验01.pptVIP

课程安排 第3章 动态规划 完全加括号的矩阵连乘积 完全加括号的矩阵连乘积可递归地定义为： 单个矩阵是完全加括号的； 矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=(BC) 设有四个矩阵A, B, C, D，总共有五中完全加括号的方式: (A((BC)D)) (A(B(CD))) ((AB)(CD)) (((AB)C)D) ((A(BC)D)) 完全加括号的矩阵连乘积 设有四个矩阵A, B, C, D，它们的维数分别是： A=50×10, B=10×40, C=40×30, D=30×5 矩阵A和B可乘的条件是: 矩阵A的列数等于矩阵B的行数. 设A是p×q的矩阵, B是q×r的矩阵, 则乘积是p×r的矩阵;计算量是pqr. 上述5种完全加括号方式的计算工作量为: (A((BC)D)), (A(B(CD))), ((AB)(CD)), (((AB)C)D), ((A(BC)D)) 16000, 10500, 36000, 87500, 34500 BC: 10×40×30 = 12000, (BC)D: 10×30×5 = 1500, (A((BC)D)): 50×10×5 = 2500 示例 示例 矩阵连乘问题 定义：给定n个矩阵{A1,A2,…,An}，其中Ai与Ai+1是可乘的，i=1,2,…n-1。考察这n个矩阵的连乘积A1A2…An。 由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。 若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积 矩阵连乘问题 给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1，2…，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少？ 穷举法：列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。 矩阵连乘问题 穷举法 动态规划 将矩阵连乘积AiAi+1…Aj 简记为A[i:j], 这里i≤j; 考察计算A[i:n]的最优计算次序。 设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，1≤kn，则其相应完全加括号方式为(A1A2…Ak)(Ak+1Ak+2…An) 计算量：A[1:k]的计算量加上A[k+1:n]的计算量，再加上A[1:k]和A[k+1:n]相乘的计算量 分析最优解的结构 特征：计算A[1:n]的最优次序所包含的计算矩阵子链 A[1:k]和A[k+1:n]的次序也是最优的。 矩阵连乘计算次序问题的最优解包含着其子问题的最优解。 这种性质称为最优子结构性质。 问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。 建立递归关系 设计算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 时， 这里Ai的维数是Pi-1×Pi 可以递归地定义m[i,j]为： 建立递归关系 m[i][j]给出了最优值，最优断开位置为k： 若将对应于m[i, j]的断开位置k记为s[i, j], 在计算出最优值m[i, j]后,可递归的由s[i, j]构造出相应的最优解. 计算最优值 对于1≤i≤j≤n不同的有序对(i,j)对应于不同的子问题。因此，不同子问题的个数最多只有 在递归计算时，许多子问题被重复计算多次。这也是该问题可用动态规划算法求解的又一显著特征。 用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。 在计算过程中，保存已解决的子问题答案。 每个子问题只计算一次，在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法。 计算最优值 void MatrixChain(int *p，int n，int **m，int **s) { for (int i = 1; i = n; i++) m[i][i] = 0; for (int r = 2; r = n; r++) for (int i = 1; i = n - r+1; i++) { int j=i+r-1; m[i][j] = m[i+1][j]+ p[i-1]*p[i]*p[j]; s[i][j] = i; for (int k = i+1