怎么查网站备案进度,做网站的工作好吗,佛山网站建设拓客科技,网络接入服务商是什么意思矩阵连乘问题----动态规划(转载)#xff1a;
给定n个矩阵#xff5b;A1,A2,…,An#xff5d;#xff0c;其中Ai与Ai1是可乘的#xff0c;i1#xff0c;2…#xff0c;n-1。如何确定计算矩阵连乘积的计算次序#xff0c;使得依此次序计算矩阵连乘积需要的数乘次数最少。… 矩阵连乘问题----动态规划(转载)
给定n个矩阵A1,A2,…,An其中Ai与Ai1是可乘的i12…n-1。如何确定计算矩阵连乘积的计算次序使得依此次序计算矩阵连乘积需要的数乘次数最少。
解答:我们按照动态规划的几个步骤来分析
1找出最优解的性质刻画其特征结构
对于矩阵连乘问题最优解就是找到一种计算顺序使得计算次数最少。
令m[i][j]表示第i个矩阵至第j个矩阵这段的最优解。
将矩阵连乘积 简记为A[i:j] 这里ij.假设这个最优解在第k处断开ikj则A[i:j]是最优的那么A[i,k]和A[k1:j]也是相应矩阵连乘的最优解。可以用反证法证明之。 这就是最优子结构也是用动态规划法解题的重要特征之一。
2建立递归关系
设计算A[i:j]1≤i≤j≤n所需要的最少数乘次数m[i,j]则原问题的最优值为m[1,n] 。
当ij时A[i,j]Ai, m[i,j]0;(表示只有一个矩阵,如A1,没有和其他矩阵相乘,故乘的次数为0)
当ij时m[i,j]min{m[i,k]m[k1,j] pi-1*pk*pj} ,其中 ikj
(相当于对i~j这段,把它分成2段,看哪种分法乘的次数最少,如A1,A2,A3,A4,则有3种分法:{A1}{A2A3A4 }、{A1A2}{A3A4 }、{A1A2A3}{A4 },其中{}表示其内部是最优解,如{A1A2A3}表示是A1A2A3的最优解),
也即 3计算最优值
对于1≤i≤j≤n不同的有序对(i,j) 对于不同的子问题因此不同子问题的个数最多只有o(n*n).但是若采用递归求解的话许多子问题将被重复求解所以子问题被重复求解这也是适合用动态规划法解题的主要特征之一。
用动态规划算法解此问题可依据其递归式以自底向上的方式进行计算。在计算过程中保存已解决的子问题答案。每个子问题只计算一次而在后面需要时只要简单查一下从而避免大量的重复计算最终得到多项式时间的算法。
下面给出动态规划求解最优值的代码
//也是要枚举求到的但是如果我们之前先记录下这些小规模的情况当求大规模的时候直接提取就行了因此体现了记忆搜索的说法
void MatrixChain(int *p,int n,int **m,int **s)
{ //m是最优值,s是最优值的断开点的索引,n为题目所给的矩阵的个数(下面例子中)
//矩阵段长度为1,则m[][]中对角线的值为0,表示只有一个矩阵,没有相乘的.
for(int i 1;in;i) m[i][i] 0;
for(int r 2;rn;r){//r表示矩阵的长度(2,3…逐渐变长) for(int i 1;in-r1;i){
//从第i个矩阵Ai开始,长度为r,则矩阵段为(Ai~Aj)
int j ir-1;//当前矩阵段(Ai~Aj)的起始为Ai,尾为Aj
//求(Ai~Aj)中最小的,其实k应该从i开始但些处先记录第一个值k从i1开始这样也可以。
//例如对(A2~A4),则i2,j4,下面一行的m[2][4]m[3][4]p[1]*p[2]*p[4],即A2(A3A4) m[i][j] m[i1][j] p[i-1]*p[i]*p[j]; s[i][j] i;//记录断开点的索引
//循环求出(Ai~Aj)中的最小数乘次数 for(int k i1 ; kj;k){
//将矩阵段(Ai~Aj)分成左右2部分(左m[i][k],右m[k1][j]), //再加上左右2部分最后相乘的次数(p[i-1] *p[k]*p[j]) int t m[i][k] m[k1][j] p[i-1] *p[k]*p[j]; if(tm[i][j]) { m[i][j] t; s[i][j] k; //保存最小的,即最优的结果
}//if }//k }//i
}//r
}//MatrixChain
上面代码中后面的k也相当于是从i到j-1递增的,只是单独把第一个(ki)提了出来.
对于 p{3035 155 10 20 25}: 计算顺序为 对上例,共6个矩阵(A1~A6),n6,当r3时,r循环里面的是3个矩阵的最优解,i从1-4,即求的是
(A1A2A3),(A2A3A4),(A3A4A5),(A4A5A6)这4个矩阵段(长度为3)的最优解.当i2时(A2A3A4)的最优解为{A2(A3A4) ,(A2A3)A4}的较小值。 •矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。
•在分析问题的最优子结构性质时所用的方法具有普遍性首先假设由问题的最优解导出的子问题的解不是最优的然后再设法说明在这个假设下可构造出比原问题最优解更好的解从而导致矛盾。
•利用问题的最优子结构性质以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。
•递归算法求解问题时每次产生的子问题并不总是新问题有些子问题被反复计算多次。这种性质称为子问题的重叠性质。
•动态规划算法对每一个子问题只解一次而后将其解保存在一个表格中当再次需要解此子问题时只是简单地用常数时间查看一下结果。
•通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间从而获得较高的解题效率。
