论坛徽章:: 13

电梯直达

1楼 [收藏(0)] [报告]

发表于 2016-01-14 11:36 |只看该作者 |倒序浏览

题目：多个矩阵相乘，按照什么顺序进行，乘法次数会最少？
相关知识：

① 矩阵可以相乘的条件是：前后两个矩阵的行列数交叉相等。比如必须3x2的矩阵才能和2x3的矩阵相乘，题目给的一组矩阵，每两个相邻矩阵都已经满足这个条件，比如A、B、C，我们不担心AB是否可以相乘、BC是否可以相乘，只需要回答先AB还是先BC。
② PxR与RxQ矩阵相乘的结果是PxQ矩阵，使用乘法的次数为PxRxQ（因为每个元素都使用了R次乘法）。

现假设有5个矩阵：a b c d e。
思路1：
对于a来说，它再不就是和b直接相乘，再不就不是，所以想到用递归解决。
但这种思路是错误的，比如：a x min(bcde)，由于min(bcde)将bcde的顺序“固定”了，假设为bx((cd)xe)，也就是a对结果的影响，仅仅考虑了它与b的关系，比如(ax(bxc))x(dxe)可能比当前得到的结果还要小呢。

思路2：
1. 将ab相乘，递归计算axb c d e相乘需要的最小乘法次数min1；
2. 将bc相乘，递归计算a bxc d e相乘需要的最小乘法次数min2；
3. 将cd相乘，递归计算a b cxd e相乘需要的最小乘法次数min3；
4. 将de相乘，递归计算a b c dxe相乘需要的最小乘法次数min4；
5. min1 min2 min3 min4中最小的值，即为答案。
但这种递归外面还要套个循环的，可以说效率上存在“bug”，它不只是最外层的递归循环的，里面每一层都会循环，所以问题规模稍微大一点，就解决不了实际问题了：

这个图很直观的看出来，这种思路“一直”在解决重复的问题。

思路3：
将解决子问题的过程“规划”成这样：

这样从最小的问题开始解决，并记录结果，求大问题可以直接使用而不用重复计算。
这种思路里一般不会出现递归，会看到一个二维数组被“滚动”的过程。

思考：
如果希望将思路2“进化”为思路3，需要做什么？
其实思路2中，从最外一层的递归之后，下标信息就开始破坏，“视野”也在变小：比如递归函数处理完第2层子问题bcde后，它实际解决了“1-4”子问题，但却以为解决了一个“0-3”的完整问题。所以，如果如果为递归函数添加“视野的起点”和“当前处理到的位置”参数，按道理就可以“进化”为思路3，并且应该可以很通用，不太需要“规划”哪些子问题应该先求。

规模, 如何, 左右