3.1.1矩阵连乘的问题.doc_第1页
3.1.1矩阵连乘的问题.doc_第2页
3.1.1矩阵连乘的问题.doc_第3页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

动态规划矩阵连乘的问题 看下面一个例子，计算三个矩阵连乘A1，A2，A3；维数分别为10*100 , 100*5 , 5*50按此顺序计算需要的次数（A1*A2）*A3）:10X100X5+10X5X50=7500次按此顺序计算需要的次数（A1*（A2*A3）:10X5X50+10X100X50=75000次所以问题是：如何确定运算顺序，可以使计算量达到最小化。枚举显然不可，如果枚举的话，相当于一个“完全加括号问题”，次数为卡特兰(Catalan)数,卡特兰数指数增长，必然不行。子问题状态的建模（很关键）：令mij表示第i个矩阵至第j个矩阵这段的最优解。显然如果i=j，则mij这段中就一个矩阵，需要计算的次数为0；如果ij，则mij=minmik+mk+1j+pi-1*pk*pj,其中k,在i与j之间游荡，所以i=kj ;代码实现时需要注意的问题：计算顺序！因为你要保证在计算mij查找mik和mk+1j的时候，mik和mk+1j已经计算出来了。观察坐标的关系如图：所以计算顺序如上图#includeusing namespace std;const int MAX = 100; /p用来记录矩阵的行列，main函数中有说明 /mij用来记录第i个矩阵至第j个矩阵的最优解 /s用来记录从哪里断开的才可得到该最优解 int pMAX+1,mMAXMAX,sMAXMAX; int n;/矩阵个数 void matrixChain() for(int i=1;i=n;i+)mii=0; for(int r=2;r=n;r+)/对角线循环 for(int i=1;i=n-r+1;i+)/行循环 int j = r+i-1;/列的控制 /找mij的最小值，先初始化一下，令k=i mij=mii+mi+1j+pi-1*pi*pj; sij=i; /k从i+1到j-1循环找mij的最小值 for(int k = i+1;kj;k+) int temp=mik+mk+1j+pi-1*pk*pj; if(tempmij) mij=temp; /s用来记录在子序列i-j段中，在k位置处 /断开能得到最优解 sij=k; /根据s记录的各个子段的最优解，将其输出 void traceback(int i,int j) if(i=j)return ; traceback(i,sij); traceback(sij+1,j); coutMultiply Ai,sijand Asij+1,jn; for(int i=0;ipi; /测试数据可以设为六个矩阵分别为 /A130*35,A235*15,A315*5,A45*10,A510*20,A620*25 /则p0-6=30,35,15,5,10,20,25 /输入：6 30 35 15 5 10 20 25 mat
人人文库> 全部分类> 生活休闲 > 科普知识

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论