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页

有关电子产品出口合同(1) 6页

2025年度合伙开办综合性医院合作协议书 9页

2025年度变压器转让与节能改造技术咨询服务协.. 10页

有关形象明星大赛入围佳丽活动参与合同 6页

2025年度厂房买卖定金协议书(含租赁权) 8页

2025年度南京市高端住宅出租管理服务合同 9页

2025年度医院食堂健康餐饮服务承包协议 9页

第19课《牛群》教案(冀教版初一下)doc初中语文.. 3页

部门经理执行宝典 53页

2025年度医用耗材配送与智慧医疗解决方案合作.. 9页

2025年度劳动合同解除无固定期限赔偿金计算与.. 7页

最新设备租赁合同范本(推荐阅读) 6页

2025年度办公室文员劳动合同(含员工激励与奖.. 7页

2025年度出租房屋合同汇编与租金调整机制 8页

最新版购销代理合同范本 6页

2025年度农村果园土地经营权转让与果树新品种.. 9页

2025年度农村宅基地买卖与乡村旅游开发合同 8页

2025年度农业贷款合同范本 7页

最新水电工程合同范本:条款详解 6页

2025年度兼职销售员跨渠道销售合作合同 9页

2025年度养猪场疫病防控合作协议书 9页

对外汉语中“V不了”结构偏误分析及教学设计 1页

2025年度公共场所安全防护用品供应协议 9页

最新国际租赁合同定义与案例分析 6页

最新商业租赁合同范本 6页

第三章内部审计程序 43页

最新厂房租赁合同书标准格式 6页

最新办公空间租赁合同模板 6页

2025年度俄罗斯农产品期货交易合同模板 9页