1、1課程安排課程安排78910111213141516十一月十一月十二月十二月一月一月29-45-11 12-18 19-25 26-23-910-16 17-18 24-30 31-6周四周四12節節計計601-602P PTTP PTTP PTTP PTTP P考試考試TT67節節計計603-604P PTTP PTTP PTTP PTTP P考試考試TT3完全加括號的矩陣連乘積可遞歸地定義為：完全加括號的矩陣連乘積可遞歸地定義為：n 單個矩陣是完全加括號的；單個矩陣是完全加括號的；n 矩陣連乘積矩陣連乘積A是完全加括號的，則是完全加括號的，則A可表示為可表示為2個完全加個完全加括號的矩陣連

2、乘積括號的矩陣連乘積B和和C的乘積并加括號，即的乘積并加括號，即A=(BC) 設有四個矩陣設有四個矩陣A, B, C, D，總共有五中完全加括號的方式，總共有五中完全加括號的方式:(A(BC)D)(A(B(CD)(AB)(CD)(AB)C)D)(A(BC)D)4設有四個矩陣設有四個矩陣A, B, C, D，它們的維數分別是：，它們的維數分別是：A=5010, B=1040, C=4030, D=305矩陣矩陣A和和B可乘的條件是可乘的條件是: 矩陣矩陣A的列數等于矩陣的列數等于矩陣B的行數的行數.設設A是是pq的矩陣的矩陣, B是是qr的矩陣的矩陣, 則乘積是則乘積是pr的矩陣的矩陣;計算量是

3、計算量是pqr.上述上述5種完全加括號方式的計算工作量為種完全加括號方式的計算工作量為:(A(BC)D), (A(B(CD), (AB)(CD), (AB)C)D), (A(BC)D)16000, 10500, 36000, 87500, 34500BC: 104030 = 12000, (BC)D: 10305 = 1500,(A(BC)D): 50105 = 25005示例示例6示例示例7定義：定義：給定給定n n個矩陣個矩陣AA1 1,A,A2 2,A,An n ，其中，其中A Ai i與與A Ai+1i+1是可乘的，是可乘的，i=1,2,n-1i=1,2,n-1。考察這。考察這n n個

4、矩陣的連乘積個矩陣的連乘積A A1 1A A2 2AAn n。 由于矩陣乘法滿足由于矩陣乘法滿足結合律結合律，所以計算矩陣的連乘可以有許，所以計算矩陣的連乘可以有許多多不同的不同的計算次序。這種計算次序可以用計算次序。這種計算次序可以用加括號加括號的方式來的方式來確定。確定。若一個矩陣連乘積的計算次序完全確定，也就是說該連乘若一個矩陣連乘積的計算次序完全確定，也就是說該連乘積已完全加括號，則可以依此次序反復調用積已完全加括號，則可以依此次序反復調用2 2個矩陣相乘個矩陣相乘的標準算法計算出矩陣連乘積的標準算法計算出矩陣連乘積8算法復雜度分析：算法復雜度分析：對于對于n個矩陣的連乘積，設其不同的

5、計算次序為個矩陣的連乘積，設其不同的計算次序為P(n)。由于每種加括號方式都可以分解為兩個子矩陣的加括號問題：由于每種加括號方式都可以分解為兩個子矩陣的加括號問題：(A1.Ak)(Ak+1An)可以得到關于可以得到關于P(n)的遞推式如下：的遞推式如下：)/4()(11)()(1)(2/311nnPnnknPkPnPnnk給定給定n n個矩陣個矩陣A A1 1,A,A2 2,A,An n，其中，其中A Ai i與與A Ai+1i+1是可乘的，是可乘的，i=1i=1，22，n-1n-1。如何確定計算矩陣連乘積的計算次序，。如何確定計算矩陣連乘積的計算次序，使得依此次序計算矩陣連乘積需要的數乘次數

6、最少？使得依此次序計算矩陣連乘積需要的數乘次數最少？窮舉法：窮舉法：列舉出所有可能的計算次序，并計算出每一種計列舉出所有可能的計算次序，并計算出每一種計算次序相應需要的數乘次數，從中找出一種數乘次數最少算次序相應需要的數乘次數，從中找出一種數乘次數最少的計算次序。的計算次序。9窮舉法窮舉法動態規劃動態規劃將矩陣連乘積將矩陣連乘積AiAi+1Aj 簡記為簡記為Ai:j, 這里這里ij;考察計算考察計算Ai:n的最優計算次序。的最優計算次序。設這個計算次序在矩陣設這個計算次序在矩陣Ak和和Ak+1之間將矩陣鏈斷開，之間將矩陣鏈斷開，1kn，則其相應完全加括號方式為，則其相應完全加括號方式為(A1A

7、2Ak)(Ak+1Ak+2An)計算量：計算量：A1:k的計算量加上的計算量加上Ak+1:n的計算量，再的計算量，再加上加上A1:k和和Ak+1:n相乘的計算量相乘的計算量10特征：計算特征：計算A1:n的最優次序所包含的計算矩陣子的最優次序所包含的計算矩陣子鏈鏈 A1:k和和Ak+1:n的次序也是最優的。的次序也是最優的。矩陣連乘計算次序問題的最優解包含著其矩陣連乘計算次序問題的最優解包含著其子問題子問題的的最優解。最優解。這種性質稱為這種性質稱為最優子結構性質。問題的最優子結構性質是該問題可用動態規劃算問題的最優子結構性質是該問題可用動態規劃算法求解的顯著特征。法求解的顯著特征。11設計算

8、設計算Ai:j，1ijn，所需要的最少數乘次數，所需要的最少數乘次數mi,j，則，則原問題的最優值為原問題的最優值為m1,n 當當i=j時，時，Ai:j=Ai，因此，因此，mi,i=0，i=1,2,n當當ij 時，時，這里這里Ai的維數是的維數是Pi-1Pi可以遞歸地定義可以遞歸地定義mi,j為：為：jkipppjkmkimjim1, 1,jipppjkmkimjijimjki, 1,min0,1jki 的位置只有的位置只有 種種可能可能kij 12mij給出了最優值，最優斷開位置為給出了最優值，最優斷開位置為k：若將對應于若將對應于mi, j的斷開位置的斷開位置k記為記為si, j, 在計算

9、在計算出最優值出最優值mi, j后后,可遞歸的由可遞歸的由si, j構造出相應的構造出相應的最優解最優解.jkipppjkmkimjim1, 1,13)(22nnn對于對于1ijn不同的有序對不同的有序對(i,j)對應于不同的子對應于不同的子問題。因此，不同子問題的個數最多只有問題。因此，不同子問題的個數最多只有在遞歸計算時，在遞歸計算時，許多子問題被重復計算多次。這也。這也是該問題可用動態規劃算法求解的又一顯著特征。是該問題可用動態規劃算法求解的又一顯著特征。用動態規劃算法解此問題，可依據其遞歸式以自底用動態規劃算法解此問題，可依據其遞歸式以自底向上的方式進行計算。向上的方式進行計算。在計算

10、過程中，保存已解決的子問題答案。在計算過程中，保存已解決的子問題答案。每個子問題只計算一次，在后面需要時只要簡單查一下，每個子問題只計算一次，在后面需要時只要簡單查一下，從而避免大量的重復計算，最終得到多項式時間的算法。從而避免大量的重復計算，最終得到多項式時間的算法。14rj 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; mij =

11、mi+1j+ pi-1*pi*pj; sij = i; for (int k = i+1; k j; k+) int t = mik + mk+1j + pi-1*pk*pj; if (t mij) mij = t; sij = k; 15A1A2A3A4A5A630 3535 1515 55 1010 2020 25113752010350437555427125205351000262554 3213000201535250005322min52541531521pppmmpppmmpppmmm16依據其遞歸式以自底向上的方式進行計算。依據其遞歸式以自底向上的方式進行計算。在計算過程中在計

12、算過程中 , , 保存已解決的子問題答案。保存已解決的子問題答案。每個子問題只計算一次每個子問題只計算一次 , , 而在后面需要時只要簡單查而在后面需要時只要簡單查一下一下 , ,從而避免大量的重復計算從而避免大量的重復計算, , 最終得到多項式時間最終得到多項式時間的算法。的算法。17void 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; mi

13、j = mi+1j+ pi-1*pi*pj; sij = i; for (int k = i+1; k j; k+) int t = mik + mk+1j + pi-1*pk*pj; if (t mij) mij = t; sij = k; 算法復雜度分析：算法復雜度分析：n 算法算法matrixChain的的主要計算量取決于算主要計算量取決于算法中對法中對r，i和和k的的3重重循環。循環。n 循環體內的計算量為循環體內的計算量為O(1)。n 3重循環的總次數為重循環的總次數為O(n3)。因此算法的計算因此算法的計算時間時間上界為上界為O(nO(n3 3) )。1.1. 算法所占用的算法所占

14、用的空間空間顯顯然為然為O(nO(n2 2) )。18sij已經存儲了構造最優解所需要的足夠的信息。已經存儲了構造最優解所需要的足夠的信息。每個部分的最優加括號方式可以根據數組每個部分的最優加括號方式可以根據數組s的相應元素得的相應元素得出。照此遞推下去，最終可以確定出。照此遞推下去，最終可以確定A1:n的最優完全加括的最優完全加括號方式，即構造出問題的一個最優解。號方式，即構造出問題的一個最優解。 void TraceBack(int i,int j) if(i=j) return; TraceBack(i,sij); TraceBack(sij+1,j); printf(Multiply

15、A%d,%d and A%d,%dn,i,sij,sij+1,j); 19一、最優子結構一、最優子結構矩陣連乘計算次序問題的最優解包含著其子問題的最優解。矩陣連乘計算次序問題的最優解包含著其子問題的最優解。這種性質稱為這種性質稱為最優子結構性質最優子結構性質。在分析問題的最優子結構性質時，所用的方法具有普遍性：在分析問題的最優子結構性質時，所用的方法具有普遍性：首先假設由問題的最優解導出的子問題的解不是最優的，首先假設由問題的最優解導出的子問題的解不是最優的，然后再設法說明在這個假設下可構造出比原問題最優解更然后再設法說明在這個假設下可構造出比原問題最優解更好的解，從而導致矛盾。好的解，從而導

16、致矛盾。 20一、最優子結構一、最優子結構利用問題的最優子結構性質，以自底向上的方式遞歸地從子利用問題的最優子結構性質，以自底向上的方式遞歸地從子問題的最優解逐步構造出整個問題的問題的最優解逐步構造出整個問題的最優解。最優解。最優子結構是問題能用動態規劃算法求解的最優子結構是問題能用動態規劃算法求解的前提前提。同一個問題可以有多種同一個問題可以有多種方式刻劃它的最優子結構，有些表示方式刻劃它的最優子結構，有些表示方法的求解速度更快（空間占用小，問題的維度低）方法的求解速度更快（空間占用小，問題的維度低）21二、重疊子問題二、重疊子問題遞歸算法求解問題時，每次產生的子問題并不總是新問題，遞歸算法

17、求解問題時，每次產生的子問題并不總是新問題，有些子問題被反復計算多次。有些子問題被反復計算多次。這種性質稱為子問題的這種性質稱為子問題的重疊性質重疊性質。動態規劃算法，對每一個子問題只解一次，而后將其解保存在一個表格動態規劃算法，對每一個子問題只解一次，而后將其解保存在一個表格中，當再次需要解此子問題時，只是簡單地用常數時間中，當再次需要解此子問題時，只是簡單地用常數時間查看一下查看一下結果。結果。 通常不同的子問題個數隨問題的大小呈通常不同的子問題個數隨問題的大小呈多項式多項式增長。因此用動態規劃算增長。因此用動態規劃算法只需要多項式時間，從而獲得較高的解題效率。法只需要多項式時間，從而獲得

18、較高的解題效率。 22矩陣連乘積的遞歸式計算矩陣連乘積的遞歸式計算:int RecurChain(int i，int j) if (i = j) return 0; int u = RecurChain(i，i) + RecurChain(i+1，j) + pi-1*pi*pj; sij = i; for (int k = i+1; k j; k+) int t = RecurChain(i，k) + RecurChain(k+1，j) + pi-1*pk*pj; if (t 0) return mij; if (i = j) return 0; int u = LookupChain(i，i

19、) + 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; mij = u; return u;三、備忘錄方法三、備忘錄方法備忘錄方法的控制結構與直接遞歸方法的控制結構相同，備忘錄方法的控制結構與直接遞歸方法的控制結構相同，區別在于備忘錄方法為每個解過的子問題建立了區別在于備忘錄方法為每個解過的子問題建立了備忘錄備忘錄以以備需要時查看，避免了

20、相同子問題的重復求解。備需要時查看，避免了相同子問題的重復求解。24若給定序列若給定序列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

21、和和Y的的公共子序列公共子序列。給定給定2個序列個序列X=x1,x2,xm和和Y=y1,y2,yn，找出，找出X和和Y的最長公共子序列。的最長公共子序列。 252個序列的最長公共子序列包含了這個序列的最長公共子序列包含了這2個序列的個序列的前綴的最長公共子序列前綴的最長公共子序列。最長公共子序列問題具有最長公共子序列問題具有最優子結構性質最優子結構性質。 設序列設序列X=x1,x2,xm和和Y=y1,y2,yn的最長公共子序的最長公共子序列為列為Z=z1,z2,zk ，則，則q 若若xm=yn，則，則zk=xm=yn，且，且zk-1是是xm-1和和yn-1的最長公共的最長公共子序列。子序列。q

22、 若若xmyn且且zkxm，則，則Z是是xm-1和和Y的最長公共子序列。的最長公共子序列。q 若若xmyn且且zkyn，則，則Z是是X和和yn-1的最長公共子序列。的最長公共子序列。26jijiyxjiyxjijijicjicjicjic; 0,; 0,0, 01,1max1 110由最長公共子序列問題的最優子結構性質建立子問題最優由最長公共子序列問題的最優子結構性質建立子問題最優值的遞歸關系。值的遞歸關系。用用cij記錄序列和的最長公共子序列的長度。記錄序列和的最長公共子序列的長度。 Xi=x1,x2,xi；Yj=y1,y2,yj。當當i=0或或j=0時，空序列是時，空序列是Xi和和Yj的最長公共子序列。的最長公共子序列。故此時故此時Cij=0。其它情況下，由最優子結構性質可建立遞歸關系如下：其它情況下，由最優子結構性質可建立遞歸關系如下：27void LCSLength(int m，int n，char *x，char *y，int *c，int *b) int i，j; for (i = 1; i = m; i+) ci0 = 0; for (i = 1; i = n; i+) c0i = 0; for (i = 1; i = m; i+) for (j = 1; j =cij-1) cij=ci-1j; bij=2; else cij=cij-1;