动态规划之矩阵链乘法理解

川长思鸟来 2021-09-11 01:06 872阅读 0赞

## **一.矩阵链事例** ##

![这里写图片描述][20160816173602649]  
矩阵链问题主要涉及的时在多个矩阵相乘，如何通过相乘的顺序来减少程序运行。

## **二.例题分析** ##

这次分析过程按照动态规划的三个基本条件来逐步解答：

1、寻找最优子结构：假设我们已经找到父矩阵链最优解，当我们划分到最后一步时都是两个子矩阵链（分别被括号包围）相乘，如（A1A2A3A4）（A5A6A7），此时显然外括号为父矩阵的最优括号划分。继续往下划分，（（A1A2A3）A4）（A5（A6A7）），则两个子矩阵链的划分括号必须也为他们本身的最优括号划分。因为如果子矩阵链的划分括号不是他们本身的最优括号划分时，两个子矩阵链就有另一种最优括号划分，如（A1（A2A3A4））（A5（A6A7））。那么就与我们的假设相悖。（（A1A2A3）A4）（A5（A6A7））不是我们父矩阵最优解。所以拥有最优划分的父矩阵的子矩阵链显然也拥有最优划分。

2、子问题重叠：看到步骤一是不是感觉这个问题可以使用递归来解决？显然可以。算法导论给出如下递归公式：  
![这里写图片描述][20160816173625778]  
但是我们发现递归公式中会有很多重复计算的子结构。由于k是未知，所以我们需要循环来找出最小的，但是，当k=i…..j时k每对应一个值就得继续往下递归，此时又得循环一遍k，在其中就会有许多子问题重复计算了。比如我们有这两个括号划分：  
（A1（A2A3A4））（A5（A6A7））和（A1（A2A3A4））（（A5A6）A7），此时前面子链括号划分是相同的而后面子链划分不同。如果我们使用15.12进行递归就会重复计算（A1（A2A3A4））。这正是动态规划解决的问题。

3、自底向上方法：我们前面使用的循环使用的是自上向下的方法。而动态规划使用的是自底向上的方法。也就是从最初向最后推理。如果我们简单的一直划分而不做比较的话，我们会发现划分的分支越来越多。而动态规划不同，它是在划分中把一些明显代价大的，可以比较的pk掉。从而减少分析次数，而且自底向上还避免了子问题的重复计算。而想要从底部开始就要求我们每次的划分都是最优划分，从而被下一次划分最优划分包含在所有下一次划分方法之内，这也是我们为什么首先要证明步骤一。

## **三.例题计算过程** ##

![这里写图片描述][20160816173643759]  
有上述矩阵：

第一次：我们从最初开始划分，也就是划分两个子矩阵，首先列出所有情况。  
A1A2 30\*35\*15=15750  
A2A3 35\*15\*5=2625  
A3A4 15\*5\*10=750  
A4A5 5\*10\*20=1000  
A5A6 10\*20\*25=5000  
由于我们不知道最优划分方法使用了那些上述划分，所以我们不能进行pk

第二次：划分三个子矩阵  
A1A2A3：此时注意A1A2A3有两种子结构划分，由于不管使用哪种子结构，划分后都归类到A1A2A3，也就是说A1A2A3无论有多少子结构，无论如何划分，划分后他都成为（A1A2A3）这一个整体。因此此时我们可以进行pk。（A1（A2A3））2625+30\*35\*5=7875或（（A1A2）A3）15750+30\*15\*5=18000，显然选择7875  
A2A3A4：2625+35\*5\*10=4375或750+35\*15\*10=6000，显然选择4375  
A3A4A5：750+15\*10\*20=3750或1000+15\*5\*20=2500，显然选择2500  
A4A5A6：1000+5\*20\*25=3500或5000+5\*10\*25=6250，显然选择3500

第三次：划分四个子矩阵  
A1A2A3A4：（A1A2A3）A4：7875+30\*5\*10=9375或A1（A2A3A4）：2500+35\*10\*30=13000或者（A1A2）（A3A4）：15750+750+30\*15\*10=21000显然选择9375  
A2A3A4A5：（A2A3A4）A5：4375+35\*10\*20=11375或者A2（A3A4A5）：2500+15\*20\*35=13000或（A2A3）（A4A5）：2625+1000+35\*5\*20=7125显然选择7125  
A3A4A5A6：（A3A4A5）A6：2500+15\*20\*25=10000或者A3（A4A5A6）：3500+5\*25\*15=5375或（A3A4）（A5A6）：750+5000+15\*10\*25=9500显然选择5375

第四次：划分五个子矩阵  
同理得A1A2A3A4A5：11875和A2A3A4A5A6：10500

第五次：最后对整个矩阵链进行划分。  
A1（A2A3A4A5A6）：30\*35\*25+18500=44750  
（A1A2）（A3A4A5A6）：157580+5375+30\*5\*25=32375  
（A1A2A3）（A4A5A6）：7875+3500+30\*5\*25=15125  
（A1A2A3A4）（A5A6）：9375+5000+30\*10\*25=21875  
（A1A2A3A4A5）A6：15375+30\*20\*25=30375

综上：最后选择15125.知道整个矩阵链的分配，我们就知道接下来的分配，因为我们使用的子矩阵链都是最优子结构，只需要往前找就行。最后分配：（A1（A2A3））（（A4A5）A6）。我们观察第五次分配可以发现：最后一次矩阵相乘增加的代价分别为30\*35\*25，30\*5\*25，30\*5\*25，30\*10\*25，30\*20\*25。发现两边都是30,25.而中间在变化也就是先前k值得变化，中间值为5时比较小，而且按照子最优解必定属于父最优解，那么是不是我们一直按照最小中间值划分，就能找到最优方法呢？

## **四.与装配线调度对比** ##

装配线问题要比矩阵链问题简单，但是其实我们可以将其对比，发现二者问题是相同的。根据矩阵链的递归公式我们发现其实n矩阵链的问题从上往下划分时其实其问题出口有n-1个，也就是k=j-i=n-1个。所以我们在《例题计算过程》中在第五次划分时有5个出口（算了5次），这个和装配线最终出口只有两个类似。  
装配线问题简单在在考虑j装配站问题时，我们只需要考虑j-1站问题就行了，因为不管怎样考虑j-1站完成后就必须考虑j站，这是由于底盘加工流程决定的，你必须加工完成j-1后才能加工j。而矩阵链不同，矩阵链n划分时我们不仅有可能考虑n-1问题，还有可能包含n-2，n-3的问题。比如对其划分（A1A2A3A4）（A5A6），此时考虑的就是6-2，6-4两个子结构，这在装配线中是不能出现的。

## **五.代码** ##

![这里写图片描述][20160816173700700]

## **六.类似问题** ##

[有趣的数][Link 1]

[20160816173602649]: /images/20210520/d85a9170a1b742389550331e30720248.png
[20160816173625778]: /images/20210520/7f7258a4ca5d401ca3814a7fb580379c.png
[20160816173643759]: /images/20210520/84f3197754af4150964e22676cd4f41e.png
[20160816173700700]: /images/20210520/7be48a9986cc4d43a7b14b2400732031.png
[Link 1]: http://blog.csdn.net/qq_16234613/article/details/53055974