矩陣連乘問(wèn)題

目錄：矩陣連乘問(wèn)題：1. 描述矩陣連乘問(wèn)題2. 分析矩陣連乘問(wèn)題以及對(duì)遞歸式的推導(dǎo)（1） 直接遞歸思路（2） 備忘錄思路（3） 動(dòng)態(tài)規(guī)劃思路3. 偽代碼的方式描述算法：（1）直接遞歸算法（2）備忘錄算法（3）動(dòng)態(tài)規(guī)劃算法4. 把算法轉(zhuǎn)換成程序?qū)崿F(xiàn)的過(guò)程及結(jié)果（1）直接遞歸算法程序（2）備忘錄算法程序（3）動(dòng)態(tài)規(guī)劃算法程序1.描述矩陣連乘問(wèn)題：給定n個(gè)矩陣，其中和是可乘的，i=1,2,n-1?？疾爝@n個(gè)矩陣的連乘積。由于矩陣乘法具有結(jié)合律，故計(jì)算矩陣的連乘積可以有許多不同的計(jì)算次序。這種計(jì)算次序可以用加括號(hào)的方式來(lái)確定。若一個(gè)矩陣連乘積的計(jì)算次序完全確定，也就是說(shuō)連乘積已完全加括號(hào)，則可依次序反復(fù)調(diào)用2個(gè)矩陣相乘的標(biāo)準(zhǔn)算法計(jì)算出矩陣連乘積。完全加括號(hào)的矩陣連乘可遞歸地定義為：（1）單個(gè)矩陣是完全加括號(hào)的；（2）矩陣連乘積A是完全加括號(hào)的，則A可表示為2個(gè)完全加括號(hào)的矩陣連乘B和C的乘積并加括號(hào)，即A=（BC）。矩陣A和B可乘的條件是矩陣A的列數(shù)等于矩陣B的行數(shù)。若A是一個(gè)pq的矩陣，B是一個(gè)qr的矩陣，那么C=AB就是一個(gè)pr矩陣。它的計(jì)算是三重循環(huán)的，計(jì)算量是pqr。如果加括號(hào)后矩陣的量是不同的，所以我們的問(wèn)題就是要討論如何給連乘的矩陣加括號(hào)才能使矩陣的計(jì)算量最少。窮舉搜索法：對(duì)于n個(gè)矩陣的連乘積，設(shè)有不同的計(jì)算次序P(n)。由于可以先在第k個(gè)和第k+1個(gè)矩陣之間將原矩陣序列分為兩個(gè)矩陣子序列，k=1,2,.,n-1；然后分別對(duì)這兩個(gè)矩陣子序列完全加括號(hào)；最后對(duì)所得的結(jié)果加括號(hào)，得到原矩陣序列的一種完全加括號(hào)方式。由此可得P(n)的遞歸式如下： 1 n=1P（n）= n1 解此遞歸方程可得，P(n)=C(n-1),而C(n)是一個(gè)指數(shù)增長(zhǎng)的函數(shù)。因此窮舉搜索法不是一個(gè)有效的算法。以下將用三種方法來(lái)解決矩陣連乘問(wèn)題的最優(yōu)加括號(hào)方式以及最優(yōu)解。2. 分析矩陣連乘問(wèn)題以及對(duì)遞歸式的推導(dǎo)將矩陣連乘積簡(jiǎn)記為Ai:j?？疾煊?jì)算A1:n的最優(yōu)計(jì)算次序。這個(gè)問(wèn)題的一個(gè)關(guān)鍵特征是：計(jì)算A1:n的最優(yōu)次序包含的計(jì)算矩陣子鏈A1:k和Ak+1:n的次序也是最優(yōu)的。這是因?yàn)椋憾x矩陣Ai的維數(shù)為pi-1pi,則Ai:k的計(jì)算次數(shù)為pi-1pk，Ak+1,j的計(jì)算次數(shù)為pkpj，而這兩個(gè)總的矩陣最后相乘時(shí)的計(jì)算量是固定的，為pi-1pkpj。所以，矩陣連乘計(jì)算次序問(wèn)題的最優(yōu)解包含著其子問(wèn)題的最優(yōu)解。這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)。（1）、直接遞歸的思路：記計(jì)算Ai:j，1ijn，所需最少數(shù)乘次數(shù)為mij,則原問(wèn)題的最優(yōu)質(zhì)為m1n。由分析得知：mij可以遞歸的定義為： 0 i=jmij= i1因此，當(dāng)n1時(shí)，T(n)n+2據(jù)此，可用數(shù)學(xué)歸納法證明T(n)2n-1=。直接遞歸法的計(jì)算時(shí)間隨n的增長(zhǎng)指數(shù)增長(zhǎng)。（2）、備忘錄方法的思路：備忘錄方法為每個(gè)子問(wèn)題建立一個(gè)記錄項(xiàng)，初始化時(shí)，該記錄項(xiàng)存入一個(gè)特殊的值，表示該問(wèn)題尚未求解。在求解過(guò)程中，對(duì)每個(gè)待求的子問(wèn)題，首先查看其相應(yīng)的記錄項(xiàng)。若記錄項(xiàng)中存儲(chǔ)的是初始化時(shí)存入的特殊值，則表示該問(wèn)題第一次遇到，此時(shí)計(jì)算出該子問(wèn)題的解，并保存在相應(yīng)的記錄項(xiàng)中，以備以后查看。若記錄項(xiàng)中存儲(chǔ)的不是初始化存入的特殊值，（比如初始化為-1，解答后賦值為0），則表示該問(wèn)題已被計(jì)算過(guò)，其相應(yīng)的記錄項(xiàng)中存儲(chǔ)的應(yīng)該是該子問(wèn)題的解答。此時(shí)，只要從記錄相中取出該子問(wèn)題的解答即可，而不必重新計(jì)算。備忘錄方法的計(jì)算量：因?yàn)槭且?jì)算mij, 因此只要從n個(gè)變量中任意選出2個(gè)分別作為i，j，則共有種選法，即有個(gè)子問(wèn)題；當(dāng)i=j時(shí)有n種選法，所以總的子問(wèn)題就為：+n=個(gè)。每填入一個(gè)記錄項(xiàng)，就要花費(fèi)O（n）的時(shí)間，所以備忘錄方法的時(shí)間復(fù)雜度為O(n3)。（3）、動(dòng)態(tài)規(guī)劃方法的思路：（以6個(gè)矩陣相乘為例）mij123456102x03xx04xxx05xxxx06xxxxx0注意，在mij中，如果ij是沒(méi)有意義的，因此在表格中都即為x；而且，如果i=j，則代表單個(gè)矩陣，所以mii=1.根據(jù)直接遞歸的方法的思路，如果要求mij,就必須要求mik和mk+1j,根據(jù)mij的矩陣，則如果要求解m12，則需要知道m(xù)11和m12；如果要求解m13，則要知道m(xù)11、m12和m11和m23;以此類推。通過(guò)此規(guī)律可以總結(jié)出要求某一個(gè)元素，就要知道其左方的所有元素的值和其下方的所有元素的值。mij123456102x03xx04xxx05xxxx06xxxxx0動(dòng)態(tài)規(guī)劃就是按照上圖所畫的形式進(jìn)行求解，從左下方求到右上方。動(dòng)態(tài)規(guī)劃算法的計(jì)算量主要取決于程序中對(duì)行、列和加括號(hào)的位置k的三重循環(huán)。循環(huán)體內(nèi)的計(jì)算量為O(1),而三重循環(huán)的總次數(shù)為O(n3)。因此該算法的計(jì)算時(shí)間上界為O(n3)。和備忘錄的算法的時(shí)間復(fù)雜度一樣，都比直接遞歸的窮舉搜索法有效得多。3. 偽代碼的方式描述算法：（1） 直接遞歸算法： int RecurMatrixChain(int i,int j)if(i=j) return 0;int u=RecurMatrixChain(i,i)+RecurMatrixChain(i+1,j)+pi-1*pi*pj;/遞歸，p 為維數(shù)sij=i;/記錄加括號(hào)的位置for(int k=i+1;kj;k+)int t=RecurMatrixChain(i,k)+RecurMatrixChain(k+1,j)+pi-1*pk*pj;/遞歸if(tu) u=t; sij=k;/判斷哪個(gè)值更小，選取哪個(gè)return 0;（2） 備忘錄算法：int MemoizedMatrixChain(int n,int * * m,int * * s)for(int i=1;i=n;i+)for(int j=i;j0) return mij; /如果是已經(jīng)解決的問(wèn)題，則標(biāo)記記錄項(xiàng)mij已經(jīng)有值,且大于0，避免重復(fù)計(jì)算。if(i=j) return 0;int u=LookupChain(i,i)+LookupChain(i+1,j)+pi-1*pi*pj;/遞歸sij=i;for(int k=i+1;kj;k+)int t=LookupChain(i,k)+LookupChain(k+1,j)+pi-1*pk*pj;/遞歸 if(tu) u=t; sij=k; /找最小值mij=u;return u;（3） 動(dòng)態(tài)規(guī)劃算法：void MatrixChain(int *p,int n,int * *m,int * *s)for(int i=1;i=n;i+) mii=0;for(int r=2;r=n;r+) for(int i=1;i=n-r+1;i+)int j=i+r-1;/具體推導(dǎo)由來(lái)見(jiàn)下圖mij=mi+1j+pi-1*pi*pj;sij=i;for(int k=i+1;kj;k+) int t=mik+k+1j+pi-1*pk*pj; if(tmij)mij=t; sij=k;/sij記錄加括號(hào)的位置下面的算法Traceback按算法MatrixChain計(jì)算出的斷點(diǎn)矩陣s指示的加括方式輸出計(jì)算Ai:j的最優(yōu)計(jì)算次序：void Traceback(int i,int j,int * *s)if(i=j) return;Traceback(i,sij,s);/遞歸地對(duì)左邊進(jìn)行加括號(hào) Traceback(sij+1,j,s);/遞歸地對(duì)右邊進(jìn)行加括號(hào)coutMultiply Aiisij;coutand A(sij+1),jendl;/輸出最優(yōu)值和最優(yōu)解。4. 把算法轉(zhuǎn)換成程序?qū)崿F(xiàn)的過(guò)程及結(jié)果程序源代碼：matrix.h#include using namespace std;#define NUM 100int mNUMNUM,sNUMNUM,pNUM;/m代洙?表括?最?小?數(shù)簓乘?次?數(shù)簓的?矩?陣；?s記?錄?的?是?最?佳?加括?號(hào)?的?位?置?；?p表括?示?矩?陣的?維?數(shù)簓,Ai的?維?數(shù)簓為 n;/備?忘?錄?方?法?int LookupChain(int i,int j)if (mij0) return mij;if (i = j)return 0;int u=LookupChain(i, i)+LookupChain(i+1,j)+pi-1*pi*pj;sij=i;for (int k=i+1; kj;k+) int t=LookupChain(i,k)+LookupChain(k+1,j)+pi-1*pk*pj; if (tu) u=t; sij=k; mij=u; return u; int MemoizedMatrixChain(int n,int * * m,int * * s)for(int i=1;i=n;i+)for(int j=i;j=n;j+) mij=0; /把?mij的?矩?陣的?上?三角?全?部?賦3值為a0。 return LookupChain(1,n);/動(dòng)態(tài)?規(guī)?劃?法?void MatrixChain() for(int i=1;i=n;i+)mii=0;for(int r=2;r=n;r+) for(int i=1;i=n-r+1;i+) int j = r+i-1; mij=mii+mi+1j+pi-1*pi*pj; sij=i; for(int k = i+1;kj;k+) int temp=mik+mk+1j+pi-1*pk*pj; if(tempmij) mij=temp; sij=k; /直接遞蘗歸法? int RecurMatrixChain(int i,int j)if(i=j) return 0;int u=RecurMatrixChain(i,i)+RecurMatrixChain(i+1,j)+pi-1*pi*pj;/遞蘗歸，?p 為a維?數(shù)簓sij=i;/記?錄?加括?號(hào)?的?位?置?for(int k=i+1;kj;k+) int t=RecurMatrixChain(i,k)+RecurMatrixChain(k+1,j)+pi-1*pk*pj;/遞蘗歸if(tu) u=t; sij=k;/判D斷?哪?個(gè)?值更小?，?選?取?哪?個(gè)?return u;void Traceback(int i,int j) if(i = j) /如?果?只?有瓺一?個(gè)?矩?陣，?則直接輸?出? coutAi; else if(i+1 = j) /加括?號(hào)?輸?出? cout(AiAj); else cout(; Traceback(i,sij); Traceback(sij+1,j); cout); MatrixMultiply.cpp#include #include matrix.husing namespace std;/int n; /定義?一?個(gè)?全?局?變?量?int main() L:int choice;coutn;cout請(qǐng)輸入第1個(gè)矩陣行數(shù)和第1個(gè)矩陣到第n個(gè)矩陣的列數(shù)：;for(int i=0;ipi;coutendl;cout請(qǐng)選擇矩陣連乘的算法:endl;cout1.備忘錄算法endl;cout2.直接遞歸算法endl;cout3.動(dòng)態(tài)規(guī)劃算法endl;cout4.重新輸入矩陣endl;cout5.退出程序endl; coutendl;coutchoice;coutendl;while(choice!=5)switch(choice)case 1: LookupChain(1,n);cout動(dòng)態(tài)規(guī)劃算法：endl;cout矩陣連乘的最優(yōu)值為：m1nendl; cout矩陣連乘的最優(yōu)解為：;Traceback(1,n);coutendl;break;case 2: RecurMatrixChain(0,n); cout動(dòng)態(tài)規(guī)劃算法：endl;cout矩陣連乘的最優(yōu)值為：m1nendl; cout矩陣連乘的最優(yōu)解為：;Traceback(1,n);coutendl;break;case 3:MatrixChain();cout動(dòng)態(tài)規(guī)劃算法：endl;cout矩陣連乘的最優(yōu)值為：m1