ACM競賽備戰(zhàn)資料精選--動態(tài)規(guī)劃之矩陣連乘.doc

動態(tài)規(guī)劃之矩陣連乘新一篇:動態(tài)創(chuàng)建二維數(shù)組作者：liguisenBlog：/liguisen以下內(nèi)容參考（摘抄）算法設(shè)計與分析，王曉東編著，清華大學(xué)出版社2003年1月第1版。給定n個矩陣A1,A2,An，其中Ai與Ai+1是可乘的，i=1,2,n-1。考察這n個矩陣的連乘積A1A2An。由于矩陣乘法滿足結(jié)合律，故計算矩陣的連乘積可以有許多不同的計算次序，這種計算次序可以用加括號的方式來確定。若一個矩陣連乘積的計算次序完全確定，則可以依此次序反復(fù)調(diào)用2個矩陣相乘的標(biāo)準(zhǔn)算法（有改進(jìn)的方法，這里不考慮）計算出矩陣連乘積。若A是一個pq矩陣，B是一個qr矩陣，則計算其乘積C=AB的標(biāo)準(zhǔn)算法中，需要進(jìn)行pqr次數(shù)乘。矩陣連乘積的計算次序不同，計算量也不同，舉例如下：先考察3個矩陣A1,A2,A3連乘，設(shè)這三個矩陣的維數(shù)分別為10100，1005，550。若按（A1A2）A3）方式需要的數(shù)乘次數(shù)為101005105507500，若按（A1（A2A3）方式需要的數(shù)乘次數(shù)為100550101005075000。下面使用動態(tài)規(guī)劃法找出矩陣連乘積的最優(yōu)計算次序。1， 設(shè)矩陣連乘積AiAi+1Aj簡記為Ai:j，設(shè)最優(yōu)計算次序在Ak和Ak+1之間斷開，則加括號方式為：（AiAi+1Ak）（Ak+1Aj）則依照這個次序，先計算Ai:k和AK+1:j然后再將計算結(jié)果相乘，計算量是：Ai:k的計算量加上AK+1:j的計算量再加上它們相乘的計算量。問題的一個關(guān)鍵是：計算Ai:j的最優(yōu)次序所包含的兩個子過程（計算Ai:k和AK+1:j）也是最優(yōu)次序。2， 設(shè)計算Ai:j所需的最少數(shù)乘次數(shù)為mij。i=j時為單一矩陣，則mii=0，ij時，設(shè)最優(yōu)計算次序在Ak和Ak+1之間斷開，則mij=mik+mk+1j+pipk+1pj+1，其中p表示數(shù)組的維數(shù)，例如A0到A5共6個數(shù)組（為了C語言的描述方便，下標(biāo)從0開始），他們表示如下：/p0:第一個矩陣的行數(shù)/p1:第一個矩陣的列數(shù)，第二個矩陣的行數(shù)/p2:第二個矩陣的列數(shù)，第三個矩陣的行數(shù)k此時并未確定，需要從i到j(luò)-1遍歷以尋找一個最小的mij。我們把這個最小的k放在sij。以下是完整實現(xiàn)代碼，以一個具體的例子實現(xiàn)，稍加修改即可通用。#include using namespace std;/MatrixChain計算mij所需的最少數(shù)乘次數(shù)/并記錄斷開位置sij/void MatrixChain(int *p,int n,int *m,int *s)for(int i=0;in;i+)mii=0;/單個矩陣相乘，所需數(shù)乘次數(shù)為/以下兩個循環(huán)是關(guān)鍵之一，以個數(shù)組為例(為描述方便，mij用ij代替)/需按照如下次序計算/01 12 23 34 45/02 13 24 35/03 14 25/04 15/05/下面行的計算結(jié)果將會直接用到上面的結(jié)果。例如要計算，就會用到，或者，或者，或者，等等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(luò)-1）斷開，即（Ai.Ak)*（Ak+1.Aj）int t=mik+mk+1j+pi*pk+1*pj+1;if(tmij)/找到更好的斷開方法mij=t;/記錄最少數(shù)乘次數(shù)sij=k;/記錄斷開位置/如果使用下面注釋的循環(huán)，則是按照如下次序計算/01 02 03 04 05/12 13 14 15/23 24 25/34 35/45/當(dāng)要計算時，會用到，而此時并沒有被計算出來。/*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;/矩陣的個數(shù)int *p=new intn+1;/p0:第一個矩陣的行數(shù)/p1:第一個矩陣的列數(shù)，第二個矩陣的行數(shù)/p2:第二個矩陣的列數(shù)，第三個矩陣的行數(shù)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