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 【所属专题】 动态规划 【适合学习阶段】 第二阶段 【解题思路】 问题分析: 存储结构: 【测试数据】 【源程序】


推荐相关:

矩阵的乘法

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


矩阵乘法

4页 2财富值 矩阵乘法6 4页 2财富值 矩阵链乘法问题 3页 1财富值 矩阵乘法的特点 1页 免费喜欢此文档的还喜欢 矩阵的乘法 24页 免费 对称矩阵 3页 1财富...


8皇后矩阵链乘

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


矩阵乘法

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


矩阵乘法

稀疏矩阵的乘法 4页 2财富值 矩阵乘法6 4页 2财富值 矩阵链乘法问题 3页 1财富值 矩阵乘法的特点 1页 免费喜欢此文档的还喜欢 Excel矩阵 10页 2财富值 矩...


阵列乘法

矩阵链乘法问题 3页 1下载券 矩阵乘法的特点 1页 免费 矩阵乘法6 4页 1下载...为了进一步提高乘法运算的 运算速度,可以采用类似于人工计算的方法,用阵列乘法器...


矩阵乘法

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


矩阵乘法

矩阵乘法6 4页 2财富值 矩阵链乘法问题 3页 1财富值 矩阵乘法的特点 1页 免费喜欢此文档的还喜欢 矩阵乘法6 4页 2财富值 矩阵的乘法 24页 免费 矩阵的乘法...


矩阵乘法

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


矩阵乘法的模型

7页 2财富值 第九章 矩阵乘法 58页 1财富值 稀疏矩阵的乘法 4页 2财富值 矩阵乘法6 4页 2财富值 矩阵链乘法问题 3页 1财富值喜欢此文档的还喜欢 ...

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