矩陣乘法的Strassen

這個算法就是在矩陣乘法中采用分治法，能夠有效的提高算法的效率。

先來看看咱們在高等代數(shù)中學(xué)的普通矩陣的乘法

兩個矩陣相乘

上邊這種普通求解方法的復(fù)雜度為: O(n3)

也稱之為暴力求解或者樸素求解

這是暴力求解的代碼，三重循環(huán)，顯然復(fù)雜度是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];

}

}

}

、

由于不滿足上邊這種復(fù)雜度太大，德國某位牛人開始找另外的解法了

先分析一下下邊的

將一個矩陣分成四塊

如上圖，A和B矩陣都被分成了四塊，該算法復(fù)雜度依然是n3，于是上邊那位老哥不服，他覺得這不是最優(yōu)的解，還有更優(yōu)的，于是他分析了上邊是四個等式，四個等式中有八個乘法，四個加法

矩陣乘法的復(fù)雜度主要就是體現(xiàn)在相乘上，而多一兩次的加法并不會讓復(fù)雜度上升太多。故此，老哥思考，是否可以讓矩陣乘法的運算過程中乘法的運算次數(shù)減少，從而達(dá)到降低矩陣乘法的復(fù)雜度，我們都知道，想要獲取時間上的效率，很多時候都是以空間換時間，于是老哥定義了七個變量

這七個變量均是矩陣，ABCDEFGH原來兩個相乘矩陣?yán)镞厔澐趾玫陌藗€小矩陣

圖三

或者看這個圖，總之七個矩陣變量是要求的(PPT上和這差不多，只是變量順序換了)

圖四

求出則七個矩陣，就能求出A*B的值

這個圖就是A*B的值，至于為什么能求出來，歸功于牛人構(gòu)造的七個巧妙的式子，利用七個式子之間的關(guān)系就求出了下邊四個變量，也就是解

圖五

最后那老哥證明了，這個復(fù)雜度是這個

圖六

順帶復(fù)習(xí)一下PPT上這個

如對于上邊圖六那個公式，a=7,k=2,b=2? 顯然7>2^2,所以套第三個T(n)

動態(tài)規(guī)劃算法

動態(tài)規(guī)劃和分治法相似，都是通過組合字問題來求解原問題，不同之處在于分治法的子問題互不干涉、互不交叉，而動態(tài)規(guī)劃相反，它會利用已經(jīng)求解的子問題進(jìn)而求解新的子問題

先舉個簡單的例子感受一蛤什么是動態(tài)規(guī)劃

錢幣問題——用面值1元、3元、5元的硬幣，如何用最少的硬幣湊到11塊錢？

第一步要想的就是，怎么把一個大問題變小問題

既然要求最少的硬幣湊到11塊錢，這里用c[i]=表示湊到i元最小要j個硬幣

那我先求最少的硬幣湊到0塊錢，顯然需要0個硬幣，所以才c[0]=0

接下來求最少的硬幣湊到1塊錢，現(xiàn)在只有面值1塊的能用，我就用一個，用完之后還需湊0元，這時才c[0]=0已知，所以才c[1]=1+c[0]=1

接下來求最少的硬幣湊到2塊錢，現(xiàn)在只有面值1塊的能用，我也先用一個，用完之后還需湊1元，這時才c[1]=1已知,所以c[2]=1+c[1]=2

接下來求最少的硬幣湊到3塊錢，現(xiàn)在有面值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)，矩陣具有結(jié)合律，所以計算的步驟有很多種選擇，但如果結(jié)合律用的不好會產(chǎn)生比較大的代價

在了解這個咱們要研究算法是干啥的之前，先了解幾個概念

1、矩陣相容：也就是兩個矩陣要能夠相乘，即A的列數(shù)等于B的行數(shù)

2、標(biāo)量乘法：若A是p*q,B是 q*r，則A*B的代價就是其標(biāo)量乘法，也就是pqr

所以要求n個給定序列的矩陣相乘的乘積，我們要研究使得該成績代價最小，也就是其標(biāo)量乘法次數(shù)之和最少(這塊最好參照一下算法導(dǎo)論211頁很詳細(xì))，說白了，就是在乘法式子中如何打括號

官方的話就不說了，直接上一串矩陣，你應(yīng)該干什么和怎么干，哈哈，怎么干

圖中給出了6個矩陣相乘，你應(yīng)該做的就是給它大括號，決定計算順序，使得計算代價最小

這個就是m[ ][ ]的算法? ? int t= m[i][k]+ m[k+1][j]+p[i-1]*p[k]*p[j]? ? ? ? ? 、

現(xiàn)在來解釋一下上邊的這個算法，我只能說老師的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]...以此類推，因為后邊計算的斜線，會用到上一條斜線上那些數(shù)

比如算m[1][3]會用到m[1][1],m[1][2],m[2][3],m[3][3]

最后解釋一下怎么找分解點，也就是在哪打括號，下邊圖的矩陣是標(biāo)記矩陣，也就是在動態(tài)規(guī)劃的過程中，你每次的最優(yōu)解是在哪劃分的它會記錄下來，如果要求A[1][6]怎么打括號，找到s[1][6]=3,然后在A[1][3]和A[3][6]里重復(fù)上邊的步驟，每個找到的點都是分界點..比如第一個找到的3

【6】】

來自moonsmile的祝福~

明天將推出貪心算法

總結(jié)

以上是生活随笔為你收集整理的矩阵相乘的strassen算法_矩阵乘法的Strassen算法+动态规划算法（矩阵链相乘和硬币问题）...的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。