算法设计与分析课件 32 矩阵连乘_第1页
算法设计与分析课件 32 矩阵连乘_第2页
算法设计与分析课件 32 矩阵连乘_第3页
算法设计与分析课件 32 矩阵连乘_第4页
算法设计与分析课件 32 矩阵连乘_第5页
已阅读5页，还剩9页未读， 继续免费阅读

下载本文档

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

文档简介

算法设计与分析本节要点CONTENTS矩阵连乘矩阵连乘给定n个矩阵{A1，A2，A3，…，An}，其中，Ai

和Ai+1（i=1，2，…，n−1）是可乘的。用加括号的方法表示矩阵连乘的次序，不同的计算次序计算量（乘法次数）是不同的，找出一种加括号的方法，使得矩阵连乘的计算量最小。A1是5×10的矩阵；A2是10×100的矩阵；A3是100×2的矩阵。（1）(A1

A2)A3运算量：5×10×100+5×100×2=6000（2）A1(A2

A3)运算量：10×100×2+5×10×2=2100矩阵连乘矩阵乘法：矩阵连乘矩阵乘法有多种运算顺序：(A1A2)(A3A4A5)

；(A1A2)(A3A4)A5；A1(A2A3)

(A4A5)；…是否可以使用动态规划？0102最优子结构子问题重叠03无后效性矩阵连乘假设AiAi+1…Aj的乘法次数是c，c=a+b+d。（1）分析最优解的结构特征假设我们已经知道了在第k个位置加括号会得到最优解，那么原问题就变成了两个子问题：(AiAi+1…Ak)，(Ak+1Ak+2…Aj)矩阵连乘（2）建立最优值递归式用m[i][j]表示AiAi+1…Aj矩阵连乘的最优值，那么两个子问题(AiAi+1…Ak)、(Ak+1Ak+2…Aj)对应的最优值分别是m[i][k]、m[k+1][j]。只需考查结果矩阵相乘的乘法次数。矩阵连乘如果用一维数组p[]来记录矩阵的行和列，第i个矩阵的行数存储在数组的第i−1位置，列数存储在数组的第i位置，那么pi*pk+1*qj对应的数组元素相乘为p[i−1]*p[k]*p[j]，原递归式变为：矩阵连乘（3）自底向上计算并记录最优值先求两个矩阵相乘的最优值，再求3个矩阵相乘的最优值，直到n个矩阵连乘的最优值。（4）构造最优解上面得到的最优值只是矩阵连乘的最小的乘法次数，并不知道加括号的次序，需要从记录表中还原加括号次序，构造最优解。矩阵连乘矩阵连乘矩阵连乘矩阵连乘构造最优解：根据最优决策数组s[][]中的数据来构造最优解，即加括号的位置。首先读取s[1][5]=4，表示在k=4的位置把矩阵分为两个子问题：(A1A2A3A4)、A5。矩阵连乘阶段（区间长度）

状态（区间起点和终点）

决策（状态转移方程）算法实现矩阵连乘算法分析时间

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

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

最新文档

评论

0/150

提交评论