矩阵连乘问题

目录：矩阵连乘问题：描述矩阵连乘问题解析矩阵连乘问题以及对递归式的推导1）直接递归思路2）备忘录思路3）动向规划思路伪代码的方式描述算法：1）直接递归算法2）备忘录算法3）动向规划算法把算法变换成程序实现的过程及结果1）直接递归算法程序2）备忘录算法程序3）动向规划算法程序描述矩阵连乘问题：给定n个矩阵{AAA}，其中AA,n-1。察看这n个矩阵1,2,ni和i1是可乘的，i=1,2,的连乘积A1,A2,An。由于矩阵乘法拥有结合律，故计算矩阵的连乘积可以有好多不相同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完好确定，也就是说连乘积已完好加括号，则可依次序屡次调用2个矩阵相乘的标准算法计算出矩阵连乘积。完好加括号的矩阵连乘可递归地定义为：（1）单个矩阵是完好加括号的；（2）矩阵连乘积A是完好加括号的，则A可表示为2个完好加括号的矩阵连乘B和C的乘积并加括号，即A=（BC）。矩阵A和B可乘的条件是矩阵A的列数等于矩阵B的行数。若A是一个p×q的矩阵，B是一个q×r的矩阵，那么C=A×B就是一个p×r矩阵。它的计算是三重循环的，计算量是pqr。若是加括号后矩阵的量是不相同的，因此我们的问题就是要谈论如何给连乘的矩阵加括号才能使矩阵的计算量最少。穷举找寻法：对于n个矩阵的连乘积，设有不相同的计算次序P(n)。由于可以先在第k个和第k+1个矩阵之间将原矩阵序列分为两个矩阵子序列，k=1,2,...,n-1；尔后分别对这两个矩阵子序列完好加括号；最后对所得的结果加括号，获取原矩阵序列的一种完好加括号方式。由此可得P(n)的递归式以下：n=1P（n）=n1P(k)P(nk)n>1k1解此递归方程可得，P(n)=C(n-1),而C(n)是一个指数增添的函数。因此穷举找寻法不是一个有效的算法。以下将用三种方法来解决矩阵连乘问题的最优加括号方式以及最优解。解析矩阵连乘问题以及对递归式的推导将矩阵连乘积Ai,Ai1,Aj简记为A[i:j]。察看计算A[1:n]的最优计算次序。这个问题的一个要点特色是：计算A[1:n]的最优次序包含的计算矩阵子链A[1:k]和A[k+1:n]的次序也是最优的。这是由于：定义矩阵A的维数为p×pi,则A[i:k]的计算次数为p×p，ii-1i-1kA[k+1,j]的计算次数为pk×pj，而这两个总的矩阵最后相乘时的计算量是固定的，为pi-1×p×p。因此，矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最kj优子构造性质。（1）、直接递归的思路：记计算A[i:j]，1≤i≤j≤n，所需最少许乘次数为m[i][j],则原问题的最优秀为m[1][n]。由解析得知：m[i][j]可以递归的定义为：0min{[][]i=j1][]}m[i][j]=[mikmkji1kji<jikjpppm[i][j]给出了最优值，即计算A[i][j]所需的最少许乘次数。同时还确定了计算A[i：j]的最优次序中的断开地址k，也就是说，对于这个k有m[i][j]=

m[i][k]

m[k

1][j]

pi

1pkpj若将对应于m[i][j]的断开地址s[i][j]构造出相应的最优解。

k记

s[i][j],

在计算出最优值

m[i][j]

后，可递归地由可以证明该算法的计算时间

T(n)

有指数下界，由算法的递归部分可得：O(1)

n=1T(n)

≥n11+(T(k)T(nk)1)n>1k1因此，当n>1时，T(n)≥n+2n1T(k)k1据此，可用数学归纳法证明T(n)≥2n-1=(2n)。直接递归法的计算时间随n的增添指数增长。（2）、备忘录方法的思路：备忘录方法为每个子问题建立一个记录项，初始化时，该记录项存入一个特其他值，表示该问题还没有求解。在求解过程中，对每个待求的子问题，第一查察其相应的记录项。若记录项中储藏的是初始化时存入的特别值，则表示该问题第一次遇到，此时计算出该子问题的解，并保存在相应的记录项中，以备今后查察。若记录项中储藏的不是初始化存入的特别值，（比方初始化为-1，解答后赋值为0），则表示该问题已被计算过，其相应的记录项中储藏的应该是该子问题的解答。此时，只要从记录相中取出该子问题的解答即可，而不用重新计算。备忘录方法的计算量：由于是要计算m[i][j],因此只要从n个变量中任意选出2个分别作为i，j，则共有Cn2种选法，即有Cn2个子问题；当i=j时有n种选法，因此总的子问题就为：Cn2+n=n(n1)个。每填入一个记录项，就要开销O（n）的时间，因此备忘录方法的时2间复杂度为O(n3)。（3）、动向规划方法的思路：（以6个矩阵相乘为例）m[i][j]123456102x03xx04xxx05xxxx06xxxxx0注意，在m[i][j]中，若是i>j是没有意义的，因此在表格中都即为x；而且，若是i=j，则代表单个矩阵，因此m[i][i]=1.依照直接递归的方法的思路，若是要求m[i][j],就必定要求m[i][k]和m[k+1][j],依照m[i][j]的矩阵，则若是要求解m[1][2]，则需要知道m[1][1]和m[1][2]；若是要求解m[1][3]，则要知道m[1][1]、m[1][2]和m[1][1]和m[2][3];以此类推。经过此规律可以总结出要求某一个元素，就要知道其左方的所有元素的值和其下方的所有元素的值。m[i][j]123456102x03xx04xxx05xxxx06xxxxx0动向规划就是依照上图所画的形式进行求解，从左下方求到右上方。动向规划算法的计算量主要取决于程序中对行、列和加括号的地址k的三重循环。循环体内的计算量为O(1),而三重循环的总次数为O(n3)。因此该算法的计算时间上界为O(n3)。和备忘录的算法的时间复杂度相同，都比直接递归的穷举找寻法有效得多。伪代码的方式描述算法：（1）直接递归算法：intRecurMatrixChain(inti,intj){if(i==j)return0;intu=RecurMatrixChain(i,i)+RecurMatrixChain(i+1,j)+p[i-1]*p[i]*p[j];intn;忘录算法"<<endl;cout<<"2.直接递归算法"<<endl;cout<<"3.动向规划算法"<<endl;cout<<"4.重新输入矩阵"<<endl;cout<<"5.退出程序"<<endl;cout<<endl;cout<<"请输入选择的编号：";cin>>choice;cout<<endl;while(choice!=5){switch(choice){case1:LookupChain(1,n);cout<<"动向规划算法："<<endl;cout<<"矩阵连乘的最优值为："<<m[1][n]<<endl;cout<<"矩阵连乘的最优解为：";Traceback(1,n);cout<<endl;break;case2:RecurMatrixChain(0,n);cout<<"动向规划算法："<<endl;cout<<"矩阵连乘的最优值为："<<m[1][n]<<endl;cout<<"矩阵连乘的最优解为：";Traceback(1,n);cout<<endl;break;case3:MatrixChain( );cout<<"动向规划算法："<<endl;cout<<"矩阵连乘的最优值为："<<m[1][n]<<endl;cout<<"矩阵连乘的最优解为：";Traceback(1,n);cout<<endl;break;case4:gotoL;break;case5:choice=4;break;default:break;}cout<<endl;cout<<"请选择矩阵连乘的算法:"<<endl;cout<<"1.