矩陣乘法的順序安排問題Python簡單實現(xiàn)

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

2、不合適的。暴力算法首先還是試探一下如何用最樸素的方式解決。設(shè)表示第個矩陣到第個矩陣的最少乘法運算次數(shù)，用數(shù)學(xué)化的語言表達我們的目標(biāo)，即minM1n,=iM1i,+Mi+1n其中、為最后兩個矩陣的大小。代碼很容易實現(xiàn)：defminMatrixMultiplication(Mats):類型的tt1矩陣乘法的最小乘法次數(shù)，及對應(yīng)的括號位置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以上算法的函數(shù)調(diào)用次數(shù)f(n)=1+f(i)+f(n-1)+f(2)+f(n-2)+.+f(n-1)+f(1),容易驗證得到f(n)=3n,即該算法的復(fù)雜度為0(3%這是不可接受的。記憶化分析一番可以發(fā)現(xiàn)，對于矩

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

5、m=*sjzforjjnrange(sjz)jnvokeCnt=0#統(tǒng)計遞歸函數(shù)重新執(zhí)行次數(shù)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)#調(diào)用次數(shù)3A8=2187prjnt(mjnMatrjxMultjpljcatjon2(Mats)(184,(2,3*(3,5*(5,8*8,2)*(2,3*3,2)*(2,5*5,3),28)注意事項Python定義二維矩陣，千萬不要使用注釋寫法。調(diào)試了很久才發(fā)現(xiàn)問題。TT正確的寫法為matrix=0*mforiinrange(n)或使用numpy庫importnumpymatrix=numpy.zeros(n,m)原因可以簡單理解為n=5m=3matrix=