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

傷城~ 2024-04-23 20:14 12阅读 0赞

![3e8eaa2f5841441b926f1469febf0df6.png][]

![95bf79a34291ffa1798cd23c19e818b2.png][]

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

![a56fa4c8b7e3a45446a4e01a024e8584.png][]

**所需的****最小乘法次数。**

**（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）是否满足重叠子问题？**

![5d3f1196ee93ceffdf9b913fd2d8c040.png][]

**如A\[1:2\]计算了2次，保存下来能够节省计算时间；**

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

#### 1.分析优化解的结构 ####

![73a142e317152c43a6e09b73865c0de0.png][]

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

![d15adcb59740530272f9e8ec7b429163.png][]

![b31a2133a4b653ccfeba65efe999a05a.png][]

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

![72856670749b3761dbd01d2fadd0b758.png][]

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

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

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

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

#### 伪代码： ####

![6b6e5a512a647f023afb5c500f5de228.png][]

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

#### 例题： ####

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

![5b46727c48695b0cb99a4c0ed6c7a760.png][]

关键在于计算出两个表格：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;
> 
> 后面以此类推：......

![8ca3d4efa02bc7d34aa506387b9580b0.png][]

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

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

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

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

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

综上，A1A2A3A4A5A6 = (A1A2)( (A3A4)(A5A6) );

[3e8eaa2f5841441b926f1469febf0df6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/fcb4f1b8e401479ebbad19c8b1fe93b9.png
[95bf79a34291ffa1798cd23c19e818b2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/73c48261132c461e989fbd7735d02eaa.png
[a56fa4c8b7e3a45446a4e01a024e8584.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/2dec6e351b2347c6ab3f71a536ae544f.png
[5d3f1196ee93ceffdf9b913fd2d8c040.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/2e1dc40ec0524d9397c98c988ddd2688.png
[73a142e317152c43a6e09b73865c0de0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/8bb65a4098984456b8a1b195304fb07f.png
[d15adcb59740530272f9e8ec7b429163.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/2cce3675fd934045b45a16e3fc112349.png
[b31a2133a4b653ccfeba65efe999a05a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/dae7a3364071440184c675855eeef16b.png
[72856670749b3761dbd01d2fadd0b758.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/3a49bcaec73e4375b3c5fe9dd096e5c3.png
[6b6e5a512a647f023afb5c500f5de228.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/4bfe79e465914d2f8d2bf963f55a41cf.png
[5b46727c48695b0cb99a4c0ed6c7a760.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/48aed890c3da4b9999924c8ded8f6e54.png
[8ca3d4efa02bc7d34aa506387b9580b0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/09b2d82e1b454ce9b4a8f491f165ec9b.png