ACM竞赛备战资料精选--动态规划之矩阵连乘.doc

动态规划之矩阵连乘新一篇:动态创建二维数组作者：liguisenBlog：/liguisen以下内容参考（摘抄）算法设计与分析，王晓东编著，清华大学出版社2003年1月第1版。给定n个矩阵A1,A2,An，其中Ai与Ai+1是可乘的，i=1,2,n-1。考察这n个矩阵的连乘积A1A2An。由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序，这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，则可以依此次序反复调用2个矩阵相乘的标准算法（有改进的方法，这里不考虑）计算出矩阵连乘积。若A是一个pq矩阵，B是一个qr矩阵，则计算其乘积C=AB的标准算法中，需要进行pqr次数乘。矩阵连乘积的计算次序不同，计算量也不同，举例如下：先考察3个矩阵A1,A2,A3连乘，设这三个矩阵的维数分别为10100，1005，550。若按（A1A2）A3）方式需要的数乘次数为101005105507500，若按（A1（A2A3）方式需要的数乘次数为100550101005075000。下面使用动态规划法找出矩阵连乘积的最优计算次序。1， 设矩阵连乘积AiAi+1Aj简记为Ai:j，设最优计算次序在Ak和Ak+1之间断开，则加括号方式为：（AiAi+1Ak）（Ak+1Aj）则依照这个次序，先计算Ai:k和AK+1:j然后再将计算结果相乘，计算量是：Ai:k的计算量加上AK+1:j的计算量再加上它们相乘的计算量。问题的一个关键是：计算Ai:j的最优次序所包含的两个子过程（计算Ai:k和AK+1:j）也是最优次序。2， 设计算Ai:j所需的最少数乘次数为mij。i=j时为单一矩阵，则mii=0，ij时，设最优计算次序在Ak和Ak+1之间断开，则mij=mik+mk+1j+pipk+1pj+1，其中p表示数组的维数，例如A0到A5共6个数组（为了C语言的描述方便，下标从0开始），他们表示如下：/p0:第一个矩阵的行数/p1:第一个矩阵的列数，第二个矩阵的行数/p2:第二个矩阵的列数，第三个矩阵的行数k此时并未确定，需要从i到j-1遍历以寻找一个最小的mij。我们把这个最小的k放在sij。以下是完整实现代码，以一个具体的例子实现，稍加修改即可通用。#include using namespace std;/MatrixChain计算mij所需的最少数乘次数/并记录断开位置sij/void MatrixChain(int *p,int n,int *m,int *s)for(int i=0;in;i+)mii=0;/单个矩阵相乘，所需数乘次数为/以下两个循环是关键之一，以个数组为例(为描述方便，mij用ij代替)/需按照如下次序计算/01 12 23 34 45/02 13 24 35/03 14 25/04 15/05/下面行的计算结果将会直接用到上面的结果。例如要计算，就会用到，或者，或者，或者，等等for(int r=1;rn;r+)for(int i=0;in-r;i+)int j=i+r;/首先在i断开，即（Ai*（Ai+1.Aj）mij=mii+mi+1j+pi*pi+1*pj+1;sij=i;for(int k=i+1;kj;k+)/然后在k（从i+1开始遍历到j-1）断开，即（Ai.Ak)*（Ak+1.Aj）int t=mik+mk+1j+pi*pk+1*pj+1;if(tmij)/找到更好的断开方法mij=t;/记录最少数乘次数sij=k;/记录断开位置/如果使用下面注释的循环，则是按照如下次序计算/01 02 03 04 05/12 13 14 15/23 24 25/34 35/45/当要计算时，会用到，而此时并没有被计算出来。/*for(int i=0;in;i+)for( int j=i+1;jn;j+)mij=mii+mi+1j+pi*pi+1*pj+1;sij=i;for(int k=i+1;kj;k+)int t=mik+mk+1j+pi*pk+1*pj+1;if(tmij)mij=t;sij=k;*/Traceback打印Ai:j的加括号方式/void Traceback(int i,int j,int *s) /sij记录了断开的位置，即计算Ai:j的加括号方式为：/(Ai:sij)*(Asij+1:j)if(i=j)return;Traceback(i,sij,s);/递归打印Ai:sij的加括号方式Traceback(sij+1,j,s);/递归打印Asij+1:j的加括号方式/能走到这里说明i等于sij，sij+1等于j/也就是说这里其实只剩下两个矩阵，不必再分了coutAi和A(sij+1)相乘endl;int _tmain(int argc, _TCHAR* argv)int n=6;/矩阵的个数int *p=new intn+1;/p0:第一个矩阵的行数/p1:第一个矩阵的列数，第二个矩阵的行数/p2:第二个矩阵的列数，第三个矩阵的行数p0=30;p1=35;p2=15;p3=5;p4=10;p5=20;p6=25;int *m,*s;m=new int*n;for( int i=0;in;i+)mi=new intn;s=new int*n;for(int i=0;in;i+)si=new intn;MatrixChain(p,n,m,s);Traceback(0,n-1,s); for(int i=0;in;i+) delete mi;mi=NULL; delete si;si=NULL; delete m; m=NULL; delete s; s = NULL; delete p; p = NULL; ret