动态规划--矩阵链相乘问题

这篇具有很好参考价值的文章主要介绍了动态规划--矩阵链相乘问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

动态规划矩阵链相乘的思路,数据结构与算法,算法分析与设计,矩阵链相乘问题,动态规划

动态规划矩阵链相乘的思路,数据结构与算法,算法分析与设计,矩阵链相乘问题,动态规划

明确原始问题A[1:n]:计算矩阵链

动态规划矩阵链相乘的思路,数据结构与算法,算法分析与设计,矩阵链相乘问题,动态规划

所需的最小乘法次数。

(1)是否满足最优子结构,问题的解是否包含子问题的优化解?

若计算A[1:n]的优化顺序在k处断开矩阵链,即A[1:n]=A[1:k]×A[k+1:n],则在A[1:n]的优化顺序中,对应于子问题A[1:k]的解必须是A[1:k]的优化解,对应A[k+1:n]的解必须是A[k+1:n]的优化解。

(2)是否满足重叠子问题?

动态规划矩阵链相乘的思路,数据结构与算法,算法分析与设计,矩阵链相乘问题,动态规划

如A[1:2]计算了2次,保存下来能够节省计算时间;

递归计算时,很多子问题会被重复计算很多次。这也是应用动态规划的特征之一

1.分析优化解的结构

动态规划矩阵链相乘的思路,数据结构与算法,算法分析与设计,矩阵链相乘问题,动态规划

2.递归定义最优解的代价

动态规划矩阵链相乘的思路,数据结构与算法,算法分析与设计,矩阵链相乘问题,动态规划

动态规划矩阵链相乘的思路,数据结构与算法,算法分析与设计,矩阵链相乘问题,动态规划

3.自底向上计算最优代价

动态规划矩阵链相乘的思路,数据结构与算法,算法分析与设计,矩阵链相乘问题,动态规划

沿对角线的方式填表!!先计算m[1,1]对角线,再计算m[1,2]对角线,以此类推,最后得到m[1,4],这就是一个自底向上的过程!

4.利用最优值的信息构造最优解

取得的k为A[i:j]最优次序中的断开位置,也即是加括号的位置,记录到s[i][j]表中。

原始问题为A[1:n],通过回溯追踪获得A[1:n]最优值时的k值,即可获得所有加括号的位置。

伪代码:

动态规划矩阵链相乘的思路,数据结构与算法,算法分析与设计,矩阵链相乘问题,动态规划

时间复杂度是O(n^3)

例题:

对维数为序列<5, 10, 3, 12, 5, 50, 6>的各矩阵,找出 矩阵链乘积的一个最优加全部括号

动态规划矩阵链相乘的思路,数据结构与算法,算法分析与设计,矩阵链相乘问题,动态规划

关键在于计算出两个表格:m[i,j]和 s[i,j] (本题都是6行6列)

i = j 时,m[i,j] = 0,所以m[1,1] = 0, m[2,2] = 0,m[3,3] = 0,m[4,4] = 0, m[5,5] = 0,                        m[6,6] = 0;


m[1,2] = min{ k=1, m[1,1] + m[2,2] + p0p1p2 = 0+0+5*10*3 } = 150;

m[2,3] = min{ k=2, m[2,2] + m[3,3] + p1p2p3 = 0+0+10*3*12 } = 360;

m[3,4] = min{ k=3, m[3,3] + m[4,4] + p2p3p4 = 0+0+3*12*5 } = 180;

m[4,5] = min{ k=4, m[4,4] + m[5,5] + p3p4p5 = 0+0+12*5*50 } = 3000;

m[5,6] = min{ k=5, m[5,5] + m[6,6] + p4p5p6 = 0+0+5*50*6 } = 1500;

m[1,3] = min{ k=1, m[1,1] + m[2,3] + p0p1p3 = 0+360+600= 960 ;

                      k=2, m[1,2] + m[3,3] + p0p2p3 = 150+0+5*3*12 = 330} = 330;

m[2,4] = min{ k=2, m[2,2] + m[3,4] + p1p2p4 = 0+180+10*3*5 = 330;

                      k=3, m[2,3] + m[4,4] + p1p3p4 = 0+360+0+10*12*5=960} = 330;

m[3,5] = min{ k=3, m[3,3] + m[4,5] + p2p3p5 = 0+3000+3*12*50 = 4800;

                      k=4, m[3,4] + m[5,5] + p2p4p5 = 180+0+3*5*50 = 930} = 930;

m[4,6] = min{ k=4, m[4,4] + m[5,6] + p3p4p6 = 0+1500+12*5*6 = 1860;

                      k=5, m[4,5] + m[6,6] + p3p5p6 = 3000+0+12*50*6 = 6600} = 1860;

后面以此类推:......

动态规划矩阵链相乘的思路,数据结构与算法,算法分析与设计,矩阵链相乘问题,动态规划

m[i, j]:记录子问题最优解的解值,保存下来避免重复计算。即矩阵连乘积A[i, j]的最小值。

i / j

1

2

3

4

5

6

1

0

150

330

405

1655

2010

2

0

360

330

1080

1950

3

0

180

930

1770

4

0

3000

1860

5

0

1500

6

0

s[i, j]:记录A[i, j]最优次序的断开位置,就是 k 的最优值。

i / j

1

2

3

4

5

6

1

0

1

2

2

4

2

2

0

2

2

2

2

3

0

3

4

4

4

0

4

4

5

0

5

6

0

所矩阵A1A2A3A4A5A6, 即矩阵连乘积A[1,6]的最少次数 = 2010;

s[1,6] = 2,A1A2A3A4A5A6 = (A1A2)A3A4A5A6;

s[3,6] = 4,A3A4A5A6 = (A3A4)(A5A6);

综上,A1A2A3A4A5A6 = (A1A2)( (A3A4)(A5A6) );文章来源地址https://www.toymoban.com/news/detail-824025.html

到了这里,关于动态规划--矩阵链相乘问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包