矩阵乘法的Strassen算法+动态规划算法（矩阵链相乘和硬币问题）
矩阵乘法的Strassen算法+动态规划算法（矩阵链相乘和硬币问题）
矩阵乘法的Strassen
这个算法就是在矩阵乘法中采用分治法，能够有效的提高算法的效率。
先来看看咱们在高等代数中学的普通矩阵的乘法
两个矩阵相乘
上边这种普通求解方法的复杂度为: O(n3)
也称之为暴力求解或者朴素求解
这是暴力求解的代码，三重循环，显然复杂度是O(n3)
、
voidMul(int** matrixA,int** matrixB,int** matrixC)
{
for(inti = 0; i < 2; ++i)
{
for(intj = 0; j < 2; ++j)
{
matrixC[i][j] = 0;
for(intk = 0; k < 2; ++k)
{
matrixC[i][j] += matrixA[i][k] * matrixB[k][j];
}
}
}
、
由于不满足上边这种复杂度太大，德国某位牛人开始找另外的解法了
先分析一下下边的
将一个矩阵分成四块
如上图，A和B矩阵都被分成了四块，该算法复杂度依然是n3，于是上边那位老哥不服，他觉得这不是最优的解，还有更优的，于是他分析了上边是四个等式，四个等式中有八个乘法，四个加法
矩阵乘法的复杂度主要就是体现在相乘上，而多一两次的加法并不会让复杂度上升太多。故此，老哥思考，是否可以让矩阵乘法的运算过程中乘法的运算次数减少，从而达到降低矩阵乘法的复杂度，我们都知道，想要获取时间上的效率，很多时候都是以空间换时间，于是老哥定义了七个变量
这七个变量均是矩阵，ABCDEFGH原来两个相乘矩阵里边划分好的八个小矩阵
图三
或者看这个图，总之七个矩阵变量是要求的（PPT上和这差不多，只是变量顺序换了）
图四
求出则七个矩阵，就能求出A*B的值
这个图就是A*B的值，至于为什么能求出来，归功于牛人构造的七个巧妙的式子，利用七个式子之间的关系就求出了下边四个变量，也就是解
图五
最后那老哥证明了，这个复杂度是这个
图六
顺带复习一下PPT上这个
如对于上边图六那个公式，a=7,k=2,b=2 显然7>2^2,所以套第三个T（n）
动态规划算法
动态规划和分治法相似，都是通过组合字问题来求解原问题，不同之处在于分治法的子问题互不干涉、互不交叉，而动态规划相反，它会利用已经求解的子问题进而求解新的子问题
先举个简单的例子感受一蛤什么是动态规划
钱币问题——用面值1元、3元、5元的硬币，如何用最少的硬币凑到11块钱？
第一步要想的就是，怎么把一个大问题变小问题
既然要求最少的硬币凑到11块钱，这里用c[i]=表示凑到i元最小要j个硬币
那我先求最少的硬币凑到0块钱，显然需要0个硬币，所以才c[0]=0
接下来求最少的硬币凑到1块钱，现在只有面值1块的能用，我就用一个，用完之后还需凑0元，这时才c[0]=0已知，所以才c[1]=1+c[0]=1
接下来求最少的硬币凑到2块钱，现在只有面值1块的能用，我也先用一个，用完之后还需凑1元，这时才c[1]=1已知,所以c[2]=1+c[1]=2
接下来求最少的硬币凑到3块钱，现在有面值1块的和三块的，如果我先用一个3块的，用完之后还需凑0元，这时才c[0]=0已知,所以c[3]=1+c[0]=1；如果我先用一个1块的，用完之后还需凑2元，这时才c[2]=2已知,所以c[3]=1+c[2]=3，取这两种中的最小的那种情况
后边的以此类推....
矩阵链乘法
如果要求n个给定序列的矩阵相乘的乘积（比如ABCDEFG），矩阵具有结合律，所以计算的步骤有很多种选择，但如果结合律用的不好会产生比较大的代价
在了解这个咱们要研究算法是干啥的之前，先了解几个概念
1、矩阵相容：也就是两个矩阵要能够相乘，即A的列数等于B的行数
2、标量乘法：若A是p*q,B是 q*r，则A*B的代价就是其标量乘法，也就是pqr
所以要求n个给定序列的矩阵相乘的乘积，我们要研究使得该成绩代价最小，也就是其标量乘法次数之和最少（这块最好参照一下算法导论211页很详细），说白了，就是在乘法式子中如何打括号
官方的话就不说了，直接上一串矩阵，你应该干什么和怎么干，哈哈，怎么干
图中给出了6个矩阵相乘，你应该做的就是给它大括号，决定计算顺序，使得计算代价最小
这个就是m[ ][ ]的算法 int t= m[i][k]+ m[k+1][j]+p[i-1]*p[k]*p[j] 、
现在来解释一下上边的这个算法，我只能说老师的PPT略傻逼，都没怎么解释
m[i][j]表示矩阵从第i个矩阵乘到第j个矩阵的最小代价
int t= m[i][k]+ m[k+1][j]+p[i-1]*p[k]*p[j] ：
上边这个算法的意思是，第i个矩阵到第k个矩阵相乘的代价+第k个矩阵到第j个矩阵相乘的代价，加上这两个乘好了的前后两个矩阵相乘的代价
然后理解了怎么算，从小到大算就OK了，按照斜线的顺序算，i和j挨着越近越好算，先算对角线，全是0，再算m[1][2],m[2][3],m[3][4]...以此类推，因为后边计算的斜线，会用到上一条斜线上那些数
比如算m[1][3]会用到m[1][1],m[1][2],m[2][3],m[3][3]
最后解释一下怎么找分解点，也就是在哪打括号，下边图的矩阵是标记矩阵，也就是在动态规划的过程中，你每次的最优解是在哪划分的它会记录下来，如果要求A[1][6]怎么打括号，找到s[1][6]=3,然后在A[1][3]和A[3][6]里重复上边的步骤，每个找到的点都是分界点..比如第一个找到的3
【6】】
来自moonsmile的祝福~
明天将推出贪心算法