算法分析與設計 矩陣連乘問題_第1頁
算法分析與設計 矩陣連乘問題_第2頁
算法分析與設計 矩陣連乘問題_第3頁
算法分析與設計 矩陣連乘問題_第4頁
算法分析與設計 矩陣連乘問題_第5頁
已閱讀5頁,還剩36頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權,請進行舉報或認領

文檔簡介

1、3.1矩陣連乘問題3.2動態(tài)規(guī)劃算法的基本要素3.3最長公共子序列3.4 0-1背包問題本章主要知識點: 動態(tài)規(guī)劃算法與分治法類似,其基本思想也是將待求解問題分解成若干個子問題nT(n/2)T(n/2)T(n/2)T(n/2)T(n)= 但是經(jīng)分解得到的子問題往往不是互相獨立的。不同子問題的數(shù)目常常只有多項式量級。在用分治法求解時,有些子問題被重復計算了許多次。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4) 如果能

2、夠保存已解決的子問題的答案,而在需要時再找出已求得的答案,就可以避免大量重復計算,從而得到多項式時間算法。 找出最優(yōu)解的性質,并刻劃其結構特征。 遞歸地定義最優(yōu)值。 以自底向上的方式計算出最優(yōu)值。 根據(jù)計算最優(yōu)值時得到的信息,構造最優(yōu)解。n給定n個矩陣 , 其中 與 是可乘的, ??疾爝@n個矩陣的連乘積 n由于矩陣乘法滿足結合律,所以計算矩陣的連乘可以有許多不同的計算次序。這種計算次序可以用加括號的方式來確定。n若一個矩陣連乘積的計算次序完全確定,也就是說該連乘積已完全加括號,則可以依此次序反復調(diào)用2個矩陣相乘的標準算法計算出矩陣連乘積,.,21nAAAiA1iA1,.,2 , 1ninAAA

3、.21(1)單個矩陣是完全加括號的;(2)矩陣連乘積 是完全加括號的,則 可 表示為2個完全加括號的矩陣連乘積 和 的乘積并加括號,即 AABC)(BCAu完全加括號的矩陣連乘積可遞歸地定義為:每一種完全加括號對應于一個矩陣連乘積得計算次序,而矩陣連乘積的計算次序與其計算量有密切的關系。下面是計算兩個矩陣乘積的標準算法:public static void matrixMultiply(double a, double b, double c, int ra, int ca, int rb, int cb) if(ca!=rb) throw new IllegalArgumentExcepti

4、on(“矩陣不可乘”); for( int i=0;ira;i+) for(int j=0;jcb;j+) int sum=ai0*b0j; for(int k=1;kca;k+) sum=sum+aik*bkj; cij=sum;設有四個矩陣 ,它們的維數(shù)分別是:DCBA , , ,1050A4010B3040C530D)(DBCA)(DCAB)(DBCA)(CDBA)(CDAB16000, 10500, 36000, 87500, 34500通過矩陣乘積標準算法可知:若矩陣A是 矩陣,B是 矩陣,則乘積C=AB是 矩陣,總共需要 次數(shù)乘得到。pqqrprpqr這樣可以計算每一種完全加括號方

5、式的計算量,如總共有五中完全加括號的方式 給定n個矩陣A1,A2,An,其中Ai與Ai+1是可乘的,i=1,2 ,n-1。如何確定計算矩陣連乘積的計算次序,使得依此次序計算矩陣連乘積需要的數(shù)乘次數(shù)最少。u窮舉法窮舉法:列舉出所有可能的計算次序,并計算出每一種計算次序相應需要的數(shù)乘次數(shù),從中找出一種數(shù)乘次數(shù)最少的計算次序。 算法復雜度分析:算法復雜度分析:對于n個矩陣的連乘積,設其不同的計算次序為P(n)。由于每種加括號方式都可以分解為兩個子矩陣的加括號問題:(A1.Ak)(Ak+1An)可以得到關于P(n)的遞推式如下:P(n)是隨n的增長呈指數(shù)增長。)/4()(11)()(1)(2/ 311

6、nnPnnknPkPnPnnku窮舉法窮舉法u動態(tài)規(guī)劃動態(tài)規(guī)劃將矩陣連乘積 簡記為Ai:j ,這里ij jiiAAA.1考察計算Ai:j的最優(yōu)計算次序。設這個計算次序在矩陣Ak和Ak+1之間將矩陣鏈斷開,ikj,則其相應完全加括號方式為).)(.(211jkkkiiAAAAAA計算量:Ai:k的計算量加上Ak+1:j的計算量,再加上Ai:k和Ak+1:j相乘的計算量 特征:計算Ai:j的最優(yōu)次序所包含的計算矩陣子鏈 Ai:k和Ak+1:j的次序也是最優(yōu)的。 矩陣連乘計算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解。這種性質稱為最優(yōu)子結構性質最優(yōu)子結構性質。問題的最優(yōu)子結構性質是該問題可用動態(tài)規(guī)劃算法

7、求解的顯著特征。n設計算Ai:j,1ijn,所需要的最少數(shù)乘次數(shù)mi,j,則原問題的最優(yōu)值為m1,n n當i=j時,Ai:j=Ai,因此,mi,i=0,i=1,2,nn當ij時,n可以遞歸地定義mi,j為:jkipppjkmkimjim1, 1,這里 的維數(shù)為 iAiipp1jipppjkmkimjijimjki, 1,min0,1jki 的位置只有 種可能kij n對于1ijn不同的有序對(i,j)對應于不同的子問題。因此,不同子問題的個數(shù)最多只有n由此可見,在遞歸計算時,許多子問題被重復計算多許多子問題被重復計算多次次。這也是該問題可用動態(tài)規(guī)劃算法求解的又一顯著特征。n用動態(tài)規(guī)劃算法解此問

8、題,可依據(jù)其遞歸式以自底向上的方式進行計算。在計算過程中,保存已解決的子問題答案。每個子問題只計算一次,而在后面需要時只要簡單查一下,從而避免大量的重復計算,最終得到多項式時間的算法)(22nnnpublic static void matrixChain(int p, int m, int s) int n=p.length-1; for (int i = 1; i = n; i+) mii = 0;/ i=j for (int r = 2; r = n; r+)/控制矩陣的鏈長度2n for (int i = 1; i = n - r+1; i+) /1=ij=n int j=i+r-1;

9、 mij = mi+1j+ pi-1*pi*pj; /k=i sij = i; for (int k = i+1; k j; k+) / ikj int t = mik + mk+1j + pi-1*pk*pj; if (t mij) mij = t; sij = k; 算法復雜度分析:算法復雜度分析:算法matrixChain的主要計算量取決于算法中對r,i和k的3重循環(huán)。循環(huán)體內(nèi)的計算量為O(1),而3重循環(huán)的總次數(shù)為O(n3)。因此算法的計算時間上界為O(n3)。算法所占用的空間顯然為O(n2)。A1A2A3A4A5A63035 3515 155 510 1020 20251137520

10、10350437555427125205351000262554 3213000201535250005322min52541531521pppmmpppmmpppmmm例如:4. 構造最優(yōu)解算法matrixChain 記錄了構造最優(yōu)解所需的全部信息。sij=k表明計算矩陣鏈Ai:j的最佳方式在矩陣Ak和Ak+1之間斷開,即最優(yōu)的加括號方式為(Ai:k)(Ak+1:j)。因此,從s1n記錄的信息可知計算A1:n的最優(yōu)加括號方式為 (A1:s1n)(As1n+1:n)。而A1:s1n的最優(yōu)加括號方式為(A1:s1s1n)(As1s1n+1:s1s1n)。 同理可以確定As1n+1:n的最優(yōu)加括號

11、方式在ss1n+1n處斷開。照此遞推下去,最終可以得到A1:n的最優(yōu)完全加括號方式,即構造出問題的一個最優(yōu)解。下面算法traceback按算法matrixChain計算出的s輸出計算Ai:j的最優(yōu)計算次序:public static void traceback(int s,int i,int j) if(i=j) return; traceback(s,i,sij); traceback(s,sij+1,j); System.out.println(“Multiply A”+i+”,”+sij+”and A”+(sij+1)+”,”+j);要輸出A1:n的最優(yōu)計算次序只需調(diào)traceback

12、(s,1,n)即可。 給定n個矩陣A1,A2,An,其中Ai與Ai+1是可乘的,i=1,2 ,n-1。如何確定計算矩陣連乘積的計算次序,使得依此次序計算矩陣連乘積需要的數(shù)乘次數(shù)最少。動態(tài)規(guī)劃動態(tài)規(guī)劃考察計算Ai:j的最優(yōu)計算次序。設這個計算次序在矩陣Ak和Ak+1之間將矩陣鏈斷開,ikj,則其相應完全加括號方式為).)(.(211jkkkiiAAAAAA計算量:Ai:k的計算量加上Ak+1:j的計算量,再加上Ai:k和Ak+1:j相乘的計算量將矩陣連乘積 簡記為Ai:j ,這里ij jiiAAA.1public static void matrixChain(int p, int m, int

13、 s) int n=p.length-1; for (int i = 1; i = n; i+) mii = 0;/ i=j for (int r = 2; r = n; r+)/控制矩陣的鏈長度2n for (int i = 1; i = n - r+1; i+) /1=ij=n int j=i+r-1; mij = mi+1j+ pi-1*pi*pj; /k=i sij = i; for (int k = i+1; k j; k+) / ikj int t = mik + mk+1j + pi-1*pk*pj; if (t mij) mij = t; sij = k; 從計算矩陣連乘積最優(yōu)

14、計算次序的動態(tài)規(guī)劃算法可以看出,動態(tài)規(guī)劃算法的有效性依賴于問題本身的兩個性質: 最優(yōu)子結構性質最優(yōu)子結構性質 子問題的重疊性質子問題的重疊性質從一般意義上,問題所具有的這兩個性質是該問題可用動態(tài)規(guī)劃算法求解的基本要素。矩陣連乘計算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解。這種性質稱為最優(yōu)子結構性質最優(yōu)子結構性質。在分析問題的最優(yōu)子結構性質時,所用的方法具有普遍性:首先假設由問題的最優(yōu)解導出的子問題的解不是最優(yōu)的,然后再設法說明在這個假設下可構造出比原問題最優(yōu)解更好的解,從而導致矛盾。 利用問題的最優(yōu)子結構性質,以自底向上的方式遞歸地從子問題的最優(yōu)解逐步構造出整個問題的最優(yōu)解。最優(yōu)子結構是問題能用

15、動態(tài)規(guī)劃算法求解的前提。注意:同一個問題可以有多種方式刻劃它的最優(yōu)子結構,有些表示方法的求解速度更快(空間占用小,問題的維度低)遞歸算法求解問題時,每次產(chǎn)生的子問題并不總是新問題,有些子問題被反復計算多次。這種性質稱為子問題的重疊性質子問題的重疊性質。動態(tài)規(guī)劃算法,對每一個子問題只解一次,而后將其解保存在一個表格中,當再次需要解此子問題時,只是簡單地用常數(shù)時間查看一下結果。 通常不同的子問題個數(shù)隨問題的大小呈多項式增長。因此用動態(tài)規(guī)劃算法只需要多項式時間,從而獲得較高的解題效率。 為了說明這一點,利用遞歸式直接計算Ai:j的遞歸算法如下:public static int recurMatrx

16、iChain(int I,int j) if(i=j) return 0; int u=recurMatrixChain(i+1,j)+pi-1*pi*pj; sij=i; 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; return u;例如:備忘錄方法的控制結構與直接遞歸方法的控制結構相同,區(qū)別在于備忘錄方法為每個解過的子問題建立了備忘錄以備需要時查看,避免了相同子問題的重復求解。另外,備忘錄方法的遞歸方式是自頂向下的,而動態(tài)規(guī)劃算

17、法是自底向上遞歸的。public static int memoizedmatrixChain(int n) for (int i=1; i =n; i+) for(int j=i;j 0) return mij;/子問題已經(jīng)被計算過 if (i = j) return 0; int u = lookupChain(i+1,j) + pi-1*pi*pj; sij = i; for (int k = i+1; k j; k+) int t = lookupChain(i,k) + lookupChain(k+1,j) + pi-1*pk*pj; if (t u) u = t; sij = k;

18、 mij = u;/保存將子問題的解 return u; 算法復雜度分析:算法復雜度分析:備忘錄算法memoizedmatrixChain的耗時為O(n3)。事實上,共有O(n2)個備忘記錄項mij,i=1,2,n,j=1,2,n。每次填入時,不包括填入記錄的時間,共耗時O(n)。 若給定序列X=x1,x2,xm,則另一序列Z=z1,z2,zk是X的子序列是指存在一個嚴格遞增下標序列i1,i2,ik使得對于所有j=1,2,k有:zj=xij。例如,序列Z=B,C,D,B是序列X=A,B,C,B,D,A,B的子序列,相應的遞增下標序列為2,3,5,7。 給定2個序列X和Y,當另一序列Z既是X的子

19、序列又是Y的子序列時,稱Z是序列X和Y的公共子序列公共子序列。 給定給定2 2個序列個序列X=xX=x1 1,x,x2 2, ,x,xm m 和和Y=yY=y1 1,y,y2 2, ,y,yn n ,找出,找出X X和和Y Y的最長公共子序列。的最長公共子序列。設序列X=x1,x2,xm和Y=y1,y2,yn的最長公共子序列為Z=z1,z2,zk ,則(1)若xm=yn,則zk=xm=yn,且Zk-1是Xm-1和Yn-1的最長公共子序列。(2)若xmyn且zkxm,則Z是Xm-1和Y的最長公共子序列。(3)若xmyn且zkyn,則Z是X和Yn-1的最長公共子序列。由此可見,2個序列的最長公共子

20、序列包含了這2個序列的前綴的最長公共子序列。因此,最長公共子序列問題具有最優(yōu)子結最優(yōu)子結構性質構性質。 由最長公共子序列問題的最優(yōu)子結構性質建立子問題最優(yōu)值的遞歸關系。用cij記錄序列和的最長公共子序列的長度。其中, Xi=x1,x2,xi;Yj=y1,y2,yj。當i=0或j=0時,空序列是Xi和Yj的最長公共子序列。故此時Cij=0。其他情況下,由最優(yōu)子結構性質可建立遞歸關系如下:jijiyxjiyxjijijicjicjicjic; 0,; 0,0, 01,1max1 110由于在所考慮的子問題空間中,總共有(mn)個不同的子問題,因此,用動態(tài)規(guī)劃算法自底向上地計算最優(yōu)值能提高算法的效率

21、。 public static int lcsLength(char x,char y,int b)1: int m=x.length-1;2: int n=y.length-1;3: int c=new intm+1n+1;4: for(int i=1;i=m;i+) ci0=0; c0i=0;5: for (int i = 1; i = m; i+)6: for (int j = 1; j =cij-1) 11: cij=ci-1j;12: bij=2;13: else 14: cij=cij-1;15: bij=3;16: return cmn;public static void lc

22、s(int i,int j,char x,int b) if (i =0 | j=0) return; if (bij= 1) lcs(i-1,j-1,x,b); System.out.print(xi); else if (bij= 2) lcs(i-1,j,x,b); else lcs(i,j-1,x,b); 4. 構造最長公共子序列構造最長公共子序列下面算法實現(xiàn)b的內(nèi)容打印出Xi和Yj的最長公共子序列。在算法lcsLength和lcs中,可進一步將數(shù)組b省去。事實上,數(shù)組元素cij的值僅由ci-1j-1,ci-1j和cij-1這3個數(shù)組元素的值所確定。對于給定的數(shù)組元素cij,可以不借助

23、于數(shù)組b而僅借助于c本身在O(1)時間內(nèi)確定cij的值是由ci-1j-1,ci-1j和cij-1中哪一個值所確定的。如果只需要計算最長公共子序列的長度,則算法的空間需求可大大減少。事實上,在計算cij時,只用到數(shù)組c的第i行和第i-1行。因此,用2行的數(shù)組空間就可以計算出最長公共子序列的長度。進一步的分析還可將空間需求減至O(min(m,n)。從計算矩陣連乘積最優(yōu)計算次序的動態(tài)規(guī)劃算法可以看出,動態(tài)規(guī)劃算法的有效性依賴于問題本身的兩個性質: 最優(yōu)子結構性質最優(yōu)子結構性質 子問題的重疊性質子問題的重疊性質從一般意義上,問題所具有的這兩個性質是該問題可用動態(tài)規(guī)劃算法求解的基本要素。備忘錄方法的控制

24、結構與直接遞歸方法的控制結構相同,區(qū)別在于備忘錄方法為每個解過的子問題建立了備忘錄以備需要時查看,避免了相同子問題的重復求解。另外,備忘錄方法的遞歸方式是自頂向下的,而動態(tài)規(guī)劃算法是自底向上遞歸的。public static int memoizedmatrixChain(int n) for (int i=1; i =n; i+) for(int j=i;j 0) return mij;/子問題已經(jīng)被計算過 if (i = j) return 0; int u = lookupChain(i+1,j) + pi-1*pi*pj; sij = i; for (int k = i+1; k j;

25、 k+) int t = lookupChain(i,k) + lookupChain(k+1,j) + pi-1*pk*pj; if (t u) u = t; sij = k; mij = u;/保存將子問題的解 return u; 若給定序列X=x1,x2,xm,則另一序列Z=z1,z2,zk是X的子序列是指存在一個嚴格遞增下標序列i1,i2,ik使得對于所有j=1,2,k有:zj=xij。例如,序列Z=B,C,D,B是序列X=A,B,C,B,D,A,B的子序列,相應的遞增下標序列為2,3,5,7。 給定2個序列X和Y,當另一序列Z既是X的子序列又是Y的子序列時,稱Z是序列X和Y的公共子序列公共子序列。 給定給定2 2個序列個序列X=xX=x1 1,x,x2 2, ,x,xm m 和和Y=yY=y1 1,y,y2 2, ,y,yn n ,找出,找出X X和和Y Y的的最長公共子序列。最長公共子序列。niiixv1maxnixCxwiniii1,1 , 01給定n種物品和一背包。物品i的重量是wi,其價值為vi,背包的容量為C。問應如何選擇裝入背包的物品,

溫馨提示

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

評論

0/150

提交評論