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


推荐相关:

矩阵链相乘问题

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


3901130814肖翰算法实验报告2

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


矩阵乘法

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


阵列乘法

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


杭电算法分析与设计复习提纲

(A,s,i,j),使之在给出矩 阵序列<A1,A2,...,An>,和由 MATRIX-CHAIN-ORDER 计算出的表 s, 以及下标 i 和 j 后, 能得出一个最优的矩阵链乘法。...


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

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


算法导论复习资料

[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步: 递归解 第3步: 算法 (二) 矩阵链乘法: 第1步: 最优子结构(顶层决策): 假设 AiAi+1…Aj 的最优分割点在 Ak 和 Ak+1 之间。其前子链 AiAi+...


实验报告

C.编写并调试程序 测试要求:元素个数不少于 10,分三种情况:k=1,k=n;k=中位数 实验项目二: 用动态规划实现矩阵链乘法问题;用动态规划算法求解最长公共 子...

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