矩阵连乘 《算法设计与分析》实验报告.doc_第1页
矩阵连乘 《算法设计与分析》实验报告.doc_第2页
矩阵连乘 《算法设计与分析》实验报告.doc_第3页
矩阵连乘 《算法设计与分析》实验报告.doc_第4页
全文预览已结束

下载本文档

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

文档简介

算法设计与分析实验报告矩阵连乘问题：给定n个矩阵A1,A2,An，其中Ai与Ai+1是可乘的，i=1,2,3,n-1。考察这n个矩阵的连乘A1,A2,An。实验基本思想：由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。设计求解矩阵连乘问题的动态规划算法的第1步是刻画该问题的最优解的结构特征。为方便起见，将矩阵连乘积简记为Ai:j。考察计算A1:n的最优计算次序。设这个计算次序矩阵在Ak和Ak+1之间将矩阵链断开，,则其相应的完全加括号方式为(A1Ak)(Ak+1An)。依此次序，先计算A1:k和Ak+1:n,然后将计算结果相乘得到A1:n。一 实验环境VC+6.0二 实验内容C语言代码如下：#include using namespace std; const int L = 7; int MatrixChain(int n,int *m,int *s,int *p); void Traceback(int i,int j,int *s);/构造最优解 int main() int pL=28,17,15,30,10,30,28; /A1为28*17 A2为17*15 A3为15*30 A4为30*10 A5为10*30 A6为30*28 int *s = new int *L; int *m = new int *L; for(int i=0;iL;i+) si = new intL; mi = new intL; cout矩阵最少的计算次数为：MatrixChain(6,m,s,p)endl; cout最优连乘顺序为：(两矩阵相乘后标号为前一个矩阵)endl; Traceback(1,6,s); return 0; int MatrixChain(int n,int *m,int *s,int *p) 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 = i+r-1; mij = mi+1j + pi-1*pi*pj; sij = i; for(int k=i+1; kj; k+) int t = mik + mk+1j + pi-1*pk*pj; if(tmij) mij = t; sij = k; return m1L-1; void Traceback(int i,int j,int *s) if(i=j) return; Traceback(i,sij,s); Traceback(sij+1,j,s); cout相乘的矩阵为 Ai,sij; cout and A(sij+1),jendl; 三 实验总结通过本次实验，我大概了解了动态规划算法的几个基本步骤。完成实验后，我认为建立递归关系是动态规划里面很关键的一步，同时也是整个动态规
人人文库> 全部分类> 行业资料 > 管理策划

温馨提示

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

最新文档

评论

0/150

提交评论