矩阵乘法的顺序安排问题Python简单实现

1、矩阵乘法的顺序安排问题python现矩阵乘法的顺序安排问题问题背景设矩阵、大小分别，则矩阵乘积需要做的标量乘法次数为。我们知道矩阵的乘法运算是不可交换的，但它是可结合的。因此对于多个矩阵的连乘，我们可以以任意顺序添加括号改变其中相邻矩阵乘法的优先级。不同计算顺序下总的标量乘法运算次数是不同的，我们的目标是找到一个最优的矩阵乘法计算顺序。给定矩阵乘法序列.将乘法序列以第个矩阵分为前后两部分，则方案数为前后两部分方案数之积。因此乘法计算的顺序个数为n丄n的解为t数，这里不加证明给出结果为n2nn+2nT(n)=Cn2n由此可见的矩阵乘法顺序个数为问题规模n的指数级，显然通过枚举找到最优的乘法顺序是

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%这是不可接受的。记忆化分析一番可以发现，对于矩

4、阵序列ij之间乘法的最优结果Mjj只有C2种，那么上述代码的中间很多段都进行了重复计算。如果把中间得到的答案记录下来，可以大大减少计算量。在不改变上述算法的框架下，将ij之间的结果Mij定义Python嵌套的内部函数。新增了变量jnvokeCnt统计递归函数需要重新计算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#统计递归函数重新执行次数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动态规划（待补充。运行对比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定义二维矩阵，千万不要使用注释写法。调试了很久才发现问题。TT正确的写法为matrix=0*mforiinrange(n)或使用numpy库importnumpymatrix=numpy.zeros(n,m)原因可以简单理解为n=5m=3matrix=