矩陣乘法的順序安排問題Python簡單實現

1、矩陣乘法的順序安排問題python現矩陣乘法的順序安排問題問題背景設矩陣、大小分別，則矩陣乘積需要做的標量乘法次數為。我們知道矩陣的乘法運算是不可交換的，但它是可結合的。因此對于多個矩陣的連乘，我們可以以任意順序添加括號改變其中相鄰矩陣乘法的優(yōu)先級。不同計算順序下總的標量乘法運算次數是不同的，我們的目標是找到一個最優(yōu)的矩陣乘法計算順序。給定矩陣乘法序列.將乘法序列以第個矩陣分為前后兩部分，則方案數為前后兩部分方案數之積。因此乘法計算的順序個數為n丄n的解為t數，這里不加證明給出結果為n2nn+2nT(n)=Cn2n由此可見的矩陣乘法順序個數為問題規(guī)模n的指數級，顯然通過枚舉找到最優(yōu)的乘法順序是

2、不合適的。暴力算法首先還是試探一下如何用最樸素的方式解決。設表示第個矩陣到第個矩陣的最少乘法運算次數，用數學化的語言表達我們的目標，即minM1n,=iM1i,+Mi+1n其中、為最后兩個矩陣的大小。代碼很容易實現：defminMatrixMultiplication(Mats):類型的tt1矩陣乘法的最小乘法次數，及對應的括號位置nttn%(Mats0.n,Mats0.motthnotthnt記錄添加的括號位置onnen(Mats)-1)tottminMatrixMultiplication(Matshtotht=minMatrixMultiplication(MatottotrightCo

3、st+Mats0.n*MattotnotnottotteftSeq+ightSeqreturnminCost,bestS測試用的矩陣類型定義如下：classMat:def_init_(self,mat=None):ifmatandisinstance(mat0,list):ttnnself.m=0def_init_(self,n,m):self.mat=self.n=nself.m=m以上算法的函數調用次數f(n)=1+f(i)+f(n-1)+f(2)+f(n-2)+.+f(n-1)+f(1),容易驗證得到f(n)=3n,即該算法的復雜度為0(3%這是不可接受的。記憶化分析一番可以發(fā)現，對于矩

4、陣序列ij之間乘法的最優(yōu)結果Mjj只有C2種，那么上述代碼的中間很多段都進行了重復計算。如果把中間得到的答案記錄下來，可以大大減少計算量。在不改變上述算法的框架下，將ij之間的結果Mij定義Python嵌套的內部函數。新增了變量jnvokeCnt統(tǒng)計遞歸函數需要重新計算M.j的次i,ji,j數。defmjnMatrjxMultjpljcatjon2(Mats):sjz=len(Mats)+1#血的教訓：不要使用下面的方法定義二維數組mjnCostMem=-1*sjz*sjzbestSeqMem=*sjz*sjzmjnCostMem=-1*sjzforjjnrange(sjz)bestSeqMe

5、m=*sjzforjjnrange(sjz)jnvokeCnt=0#統(tǒng)計遞歸函數重新執(zhí)行次數defhelper(s,t):jfs=t:return0,%d,%d%(Matss.n,Matss.m)jfmjnCostMemst!=-1:returnmjnCostMemst,bestSeqMemstnonlocaljnvokeCntjnvokeCnt+=1jmportmathmjnCost=math.jnfbestSeq=forjjnrange(s,t):leftCost,leftSeq=helper(s,j)rjghtCost,rjghtSeq=helper(j+1,t)tmpCost=left

6、Cost+rjghtCost+Matss.n*Matsj.m*Matst.mjftmpCostmjnCost:mjnCost=tmpCostbestSeq=(+leftSeq+*+rjghtSeq+)mjnCostMemst=mjnCostbestSeqMemst=bestSeqreturnmjnCost,bestSeqreturnhelper(0,len(Mats)-1),jnvokeCnt動態(tài)規(guī)劃（待補充。運行對比Mats=Mat(2,3),Mat(3,5),Mat(5,8),Mat(8,2),Mat(2,3),Mat(3,2),Mat(2,5),Mat(5,3)prjnt(mjnMatrjxMultjpljcatjon(Mats)(184,(2,3*(3,5*(5,8*8,2)*(2,3*3,2)*(2,5*5,3)#調用次數3A8=2187prjnt(mjnMatrjxMultjpljcatjon2(Mats)(184,(2,3*(3,5*(5,8*8,2)*(2,3*3,2)*(2,5*5,3),28)注意事項Python定義二維矩陣，千萬不要使用注釋寫法。調試了很久才發(fā)現問題。TT正確的寫法為matrix=0*mforiinrange(n)或使用numpy庫importnumpymatrix=numpy.zeros(n,m)原因可以簡單理解為n=5m=3matrix=