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


推荐相关:

矩阵链乘法

回专题模式 回学习阶段模式 【题目名称、来源】 最优 矩阵链乘法 (经典问题) 【问题描述】 7、矩阵链乘法 已知两个矩阵 A,B 的行列分别为 n*m 和 m*p 时...


矩阵链相乘算法

矩阵链相乘问题求解 一、 说说递归与动态规划 a) 递归 我们知道递归的思想是...。考查这 n 个矩阵的 连乘积 A1A2A3…An。由于矩阵的乘法满足结合律,故计算...


矩阵链相乘问题

矩​阵​​相​乘​问​题要找到符合要求的子问题序列,我这样想: 1、 首先 1 个矩阵的规模是知道的。 2、 2 个矩阵时时,子问题规模知道;三个...


3901130814肖翰算法实验报告2

同理可知,计算 A[1:n]的最优次序所包含的计算矩阵子链 A[k+1:n]的次序...只知道最少数乘次数,还不知道具体应按什么次 序做矩阵乘法才能达到最少的数乘...


阵列乘法

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


算法导论复习资料

[i, j] = "↑" 7 then PRINT-LCS(b, X, i - 1, j) 8 else PRINT-LCS(b, X, i, j - 1) d)矩阵链乘法的算法:参照课本上的矩阵链表得出矩阵...


算法导论课程设计

(null, "收集钱所走的路线:" + result + "\n" + "收集到的钱最大为:" + sum); result = " "; 3.算法时间复杂度分析 像在矩阵链乘法问题一样, ...


2月6日训练试题(提高班)

4.矩阵链乘法(matrix)【题目描述】 我们都知道矩阵乘法:给定两个矩阵 A 和 B,若 A 是 n*r 的矩阵,B 是 r*m 的矩阵, 则 A*B 的结果 C 是一个 n*...


西电软件学院算法实验报告

第二次试验一、 问题: Matrix-chain product 分析:本题是矩阵链乘问题,需要求出最优括号化方案。即在矩阵的乘法链上 添加括号来改变运算顺序以使矩阵链乘法的...


西电软件学院算法实验报告模板2份

(2)定义 m[i,j]为计算矩阵 Ai..j 所需标量乘法次数的最小值, 对于 i=j 时,矩阵链乘只包含唯一的矩阵 Ai,因此不需要做任何标量乘法 运算,所以 m[i,i...

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