tceic.com
学霸学习网 这下你爽了
相关标签
当前位置:首页 >> 学科竞赛 >>

矩阵链乘法


回专题模式 回学习阶段模式 【题目名称、来源】 最优 矩阵链乘法 (经典问题) 【问题描述】 7、矩阵链乘法 已知两个矩阵 A,B 的行列分别为 n*m 和 m*p 时才可以相乘,得到新的矩阵 AB,行 列值为 n*p,相乘时进行乘法的总次数为 n*m*p 次。 现 在 给 定 N 个 可 以 相 乘 的 矩 阵 构 成 一 个 链 A1,A2,…,An , 矩 阵 的 行 列 值 为 p0,p1,p2….,pn-1,pn,其中 p0,p1 为 A1 的行列值,p1,p2 为 A2 的行列值,pn-1,pn 为 An 的 行列值。 例如有 3 个矩阵组成的矩阵链 A1,A2,A3,他们的行列值为 10,100, 5 ,50,就是说 A1 的行列值为 10,100 A2 的行列值为 100,5 A3 的行列值为 5 ,50 如果按照( (A1A2)A3)的顺序做乘法, A1*A2 的乘法次数 10*100*5=5000,新矩阵 行列为 10,5。再和 A3 相乘,乘法次数为 10*5*50=2500,所以矩阵链乘法总次数为 5000+2500=7500 次。 如果按照(A1(A2A3) )的顺序做乘法,A2*A3 的乘法次数为 100*5*50=25000,新矩 阵行列为 100,50,然后用 A1 再乘以它,乘法次数为 10*100*50=50000,所以矩阵链乘法 总次数为 25000+50000=75000。是上一种方法的 10 倍。 你现在的任务是对于给定行列值的 n 个矩阵 A1A2…An, 找到一种乘法顺序, 使得总的 乘法次数最少。 输入: N 矩阵的个数 p0 p1 ……pn n+1 个数,代表 n 个矩阵的行列值 输出: 最小乘法次数 输入样例: 3 10 100 5 50 输出样例: 7500 【所属专题】 动态规划 【适合学习阶段】 第二阶段 【解题思路】 问题分析: 存储结构: 【测试数据】 【源程序】


推荐相关:

矩阵乘法

矩阵运算及其应用 68页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 矩阵乘法 矩阵乘法矩阵乘法隐藏>> 矩阵乘法 ...


矩阵乘法

18页 20财富值 矩阵 9页 2财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 矩阵乘法 隐藏>> 矩阵乘法 C++源码:...


矩阵乘法

C++矩阵乘法源程序 15页 5财富值 动态规划实现矩阵连乘 C++ 7页 2财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。...


矩阵的乘法

58页 1财富值 稀疏矩阵的乘法 4页 2财富值 矩阵乘法6 4页 2财富值 矩阵链乘法问题 3页 1财富值 矩阵乘法的特点 1页 免费喜欢...


8皇后矩阵链乘

实验步骤:1.明确实验目标和实验任务 2.理解实验所涉及到动态规划法的思想 3.编写程序实现求矩阵链乘法的最优解。 4.设计实验数据数据并运行程序,记录运行的结果 ...


阵列乘法

矩阵乘法 24页 免费 矩阵乘法 8页 1下载券 矩阵乘法 3页 1下载券 矩阵乘法 3页 4下载券 关于矩阵乘法 7页 1下载券 第九章 矩阵乘法 58页 1下载券 ...


3901130814肖翰算法实验报告2

也就是说,通过算法 matrixChain 的计算,只知道最少数乘次数,还不知道具体应按什么次 序做矩阵乘法才能达到最少的数乘次数。 事实上,算法 matrixChain 已记录了...


矩阵乘法

关于矩阵关于矩阵隐藏>> 矩阵乘法 [编辑] 一般矩阵乘积矩阵相乘最重要的方法当然是一般矩阵乘积了,它只有在第一个矩阵 的列数(column)和第二个矩阵的行数(row)...


矩阵乘法的模型

矩阵运算及其应用 90页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 矩阵乘法的模型 很强大的模型很强大的模型隐藏...


算法设计与分析 关于矩阵乘法

关于矩阵乘法假定 A, B 都是 n×n 矩阵,它们的 i 行 j 列元素分别记为 A(i,j)和 B(i,j)。 如果用 S 和 C 分别记 A+B 和 A*B, 则有 S (...

网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com