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的增长呈指数增长。

最近更新

2025年度液化气液化技术专利许可使用合同 8页

2025年ICU环境下有机磷农药中毒急救护理探讨 22页

2025年度海洋工程劳务施工合同 9页

2025年度沉浸式展厅全景图定制与安装服务合同.. 9页

2025年度汽车销售居间代理协议 9页

2023年江苏省公务员省考《行测》(A类)真题(.. 61页

2025年度汽车租赁合同车辆租赁市场分析报告范.. 9页

2025年度汽车动产质押合同——汽车维修企业质.. 9页

2025年度水果店品牌授权经营合作协议 8页

2025年CSSD高效去污消毒流程详解 22页

2025年度水利工程尾款抵账协议(含水质净化).. 8页

2025年度民宿租赁合同房东免责条款详解 7页

2025年度桶装水电商平台合作协议 9页

2022年河南省公务员省考《行测》真题(含答案.. 52页

2025年AFP检测方法与鉴别诊断要点 45页

2025年度朋友名义购置新能源车贷款服务合同 7页

2025年度智能购物中心商铺租赁合同模板 8页

2025年度智能装备股份合作协议书模板 9页

2025年 KDIGO特发性膜性肾病治疗指南详解 15页

2025年度智能硬件研发个体工商户合伙协议 9页

2025年度智能物流合伙退伙协议书版 8页

2025年度智能机器人操作员劳动合同模板电子版.. 7页

2025年度智能小区车位使用权电子租赁合同 8页

2025年度智能家居家电智能节能家装合同电子版.. 8页

2025年度智能家居全屋家具定制服务合同 9页

2025年度智能家居与智能家居系统家装施工合同.. 9页

2025年度智能城市建设项目股东个人合作协议书.. 9页

2025年度智能制造委托投资合同协议 8页

2025年无针水光产品培训课件PPT 33页

中医技能知识考试题+答案 20页