矩陣連乘問(wèn)題_第1頁(yè)
矩陣連乘問(wèn)題_第2頁(yè)
矩陣連乘問(wèn)題_第3頁(yè)
矩陣連乘問(wèn)題_第4頁(yè)
矩陣連乘問(wèn)題_第5頁(yè)
已閱讀5頁(yè),還剩6頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎ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

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論