1 / 41
文档名称:

算法分析与设计矩阵连乘问题.ppt

格式:ppt   大小:5,143KB   页数:41页
下载后只包含 1 个 PPT 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

算法分析与设计矩阵连乘问题.ppt

上传人:54156456 2025/3/15 文件大小:5.02 MB

下载得到文件列表

算法分析与设计矩阵连乘问题.ppt

相关文档

文档介绍

文档介绍:该【算法分析与设计矩阵连乘问题 】是由【54156456】上传分享,文档一共【41】页,该文档可以免费在线阅读,需要了解更多关于【算法分析与设计矩阵连乘问题 】的内容,可以使用淘豆网的站内搜索功能,选择自己适合的文档,以下文字是截取该文章内的部分文字,如需要获得完整电子版,请下载此文档到您的设备,方便您编辑和打印。本章主要知识点:
矩阵连乘问题
动态规划算法的基本要素
最长公共子序列
0-1背包问题
202X
第3章 动态规划
算法总体思想
动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题
n
T(n/2)
T(n/2)
T(n/2)
T(n/2)
T(n)
=
算法总体思想
但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时,有些子问题被重复计算了许多次。
n
T(n)
=
n/2
T(n/4)
T(n/4)
T(n/4)
T(n/4)
n/2
T(n/4)
T(n/4)
T(n/4)
T(n/4)
n/2
T(n/4)
T(n/4)
T(n/4)
T(n/4)
n/2
T(n/4)
T(n/4)
T(n/4)
T(n/4)
如果能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,就可以避免大量重复计算,从而得到多项式时间算法。
算法总体思想
01
找出最优解的性质,并刻划其结构特征。
02
递归地定义最优值。
03
以自底向上的方式计算出最优值。
04
根据计算最优值时得到的信息,构造最优解。
动态规划基本步骤
给定n个矩阵 , 其中 与 是可乘的, 。考察这n个矩阵的连乘积
由于矩阵乘法满足结合律,所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。
若一个矩阵连乘积的计算次序完全确定,也就是说该连乘积已完全加括号,则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积
3
2
1
矩阵连乘问题
完全加括号的矩阵连乘积
(1)单个矩阵是完全加括号的;
(2)矩阵连乘积 是完全加括号的,则 可
表示为2个完全加括号的矩阵连乘积 和
的乘积并加括号,即
完全加括号的矩阵连乘积可递归地定义为:
每一种完全加括号对应于一个矩阵连乘积得计算次序,
而矩阵连乘积的计算次序与其计算量有密切的关系。
下面是计算两个矩阵乘积的标准算法:
完全加括号的矩阵连乘积
public static void matrixMultiply(double a[][], double b[][], double c[][],
int ra, int ca, int rb, int cb)
{
if(ca!=rb)
throw new IllegalArgumentException(“矩阵不可乘”);

for( int i=0;i<ra;i++)
for(int j=0;j<cb;j++)
{
int sum=a[i][0]*b[0][j];
for(int k=1;k<ca;k++)
sum=sum+a[i][k]*b[k][j];
c[i][j]=sum;
}
}
设有四个矩阵 ,它们的维数分别是:
16000, 10500, 36000, 87500, 34500
通过矩阵乘积标准算法可知:若矩阵A是 矩阵,B是
矩阵,则乘积C=AB是 矩阵,总共需要
次数乘得到。
这样可以计算每一种完全加括号方式的计算量,如
总共有五中完全加括号的方式
矩阵连乘问题
给定n个矩阵{A1,A2,…,An},其中Ai与Ai+1是可乘的,i=1,2 ,…,n-1。如何确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少。
穷举法:列举出所有可能的计算次序,并计算出每一种计算次序相应需要的数乘次数,从中找出一种数乘次数最少的计算次序。
算法复杂度分析:
对于n个矩阵的连乘积,设其不同的计算次序为P(n)。
由于每种加括号方式都可以分解为两个子矩阵的加括号问题:(A1...Ak)(Ak+1…An)可以得到关于P(n)的递推式如下:
P(n)是随n的增长呈指数增长。

最近更新

大数据在商业地产项目运营中的风险预测-全面剖.. 26页

区域教育竞争格局-全面剖析 35页

间歇曝气SBR工艺处理特性及动力学研究 3页

锌铬涂层表面有机硅基封闭剂涂覆工艺研究 3页

2024初一学生入团申请书800字(31篇) 49页

2025届高考英语一轮复习知识清单——名词++ 17页

态势感知系统的自动化处理-全面剖析 25页

5月财务实习报告总结(3篇) 15页

时间序列预测的可信区间分析-全面剖析 27页

诗歌整体阅读方法 18页

项目管理在新兴技术中的机遇与挑战-全面剖析 28页

风电场经济效益评估方法-全面剖析 28页

识别客户关系管理中的客户 35页

运盐闸电气设备改造施工与质量控制对策研究 3页

迈步自移式皮带机尾的研制与应用 3页

高中写景作文400字三篇 4页

输气管道河流穿越盾构隧道设计技术研究 3页

设备资产管理系统使用指南 24页

论语(前三篇解释) 69页

路桥施工企业风险分析与经济管理中的内部控制.. 3页

超声行波微流体驱动的流动特性分析 3页

赤霉素对紫薇种子萌发和幼苗生长影响的研究 3页

贵州省侗族、土家族和仡佬族13项遗传性状分析.. 3页

财政与金融支农资源整合问题研究 3页

谈民族村寨旅游社区利益保障制度系统的研究结.. 3页

试井作业复杂情况分析与技术措施优选探讨 3页

论新规则中资产减值会计处理面临的问题及对策.. 4页

认知无线电网络信道交汇研究综述 3页

计算机在自动控制技术实践中的应用刍议 3页

西安L波段雷达观测数据实时质量控制方法 4页