遞歸、分治、動態(tài)規(guī)劃、回溯(1)(編輯修改稿)
2024-11-13 02:46 本頁面
【文章內容簡介】 積 （ 1）單個矩陣是完全加括號的； （ 2）矩陣連乘積 是完全加括號的，則 可 表示為 2個完全加括號的矩陣連乘積 和 的乘積并加括號，即 A AB C)(BCA ?DCBA , , ,1050 ??A 4010 ??B 3040 ??C 530 ??D)))((( DBCA)))( ( ( DCAB )))((( DBCA) ) )((( CDBA )))((( CDAB16000, 10500, 36000, 87500, 34500 ? 完全加括號的矩陣連乘積可遞歸地定義為： ? 設有四個矩陣 ，它們的維數分別是： ? 總共有五中完全加括號的方式 矩陣連乘問題 ? 給定 n個矩陣 ， 其中 與 是可乘的， 。考察這 n個矩陣的連乘積 ? 由于矩陣乘法滿足結合律，所以計算矩陣的連乘可以有許多不同的計算次序。這種計算次序可以用加括號的方式來確定。 ? 若一個矩陣連乘積的計算次序完全確定，也就是說該連乘積已完全加括號，則可以依此次序反復調用 2個矩陣相乘的標準算法計算出矩陣連乘積 },...,{ 21 nAAA iA 1?iA1, . . . ,2,1 ?? ninAAA ...21矩陣連乘問題 給定 n個矩陣｛ A1,A2,…,An｝，其中 Ai與 Ai+1是可乘的，i=1,2 ,…,n1。如何確定計算矩陣連乘積的計算次序，使得依此次序計算矩陣連乘積需要的數乘次數最少。 ?窮舉法 ：列舉出所有可能的計算次序，并計算出每一種計算次序相應需要的數乘次數，從中找出一種數乘次數最少的計算次序。 算法復雜度分析： 對于 n個矩陣的連乘積，設其不同的計算次序為 P(n)。 由于每種加括號方式都可以分解為兩個子矩陣的加括號問題：(A1...Ak)(Ak+1…An)可以得到關于 P(n)的遞推式如下： )/4()(11)()( 1)( 2/311nnPnnknPkPnP nnk???????????? ???矩陣連乘問題 ?窮舉法 ?動態(tài)規(guī)劃 將矩陣連乘積 簡記為 A[i:j] ，這里 i≤j jii AAA . ..1?考察計算 A[i:j]的最優(yōu)計算次序。設這個計算次序在矩陣 Ak和 Ak+1之間將矩陣鏈斷開， i≤kj，則其相應完全 加括號方式為 )...)(...( 211 jkkkii AAAAAA ???計算量： A[i:k]的計算量加上 A[k+1:j]的計算量，再加上 A[i:k]和 A[k+1:j]相乘的計算量 建立遞歸關系 ? 設計算 A[i:j]， 1≤i≤j≤n，所需要的最少數乘次數m[i,j]，則原問題的最優(yōu)值為 m[1,n] ? 當 i=j時， A[i:j]=Ai，因此， m[i,i]=0， i=1,2,…,n ? 當 ij時， ? 可以遞歸地定義 m[i,j]為： jki pppjkmkimjim 1],1[],[],[ ?????這里 的維數為 iA ii pp ??1?????????????? jipppjkmkimjijimjki }],1[],[{mi n0],[1jki 的位置只有 種 可能 k ij?計算最優(yōu)值 ? 對于 1≤i≤j≤n不同的有序對 (i,j)對應于不同的子問題。因此，不同子問題的個數最多只有 ? 由此可見，在遞歸計算時， 許多子問題被重復計算多次 。這也是該問題可用動態(tài)規(guī)劃算法求解的又一顯著特征。 ? 用動態(tài)規(guī)劃算法解此問題，可依據其遞歸式以自底向上的方式進行計算。在計算過程中，保存已解決的子問題答案。每個子問題只計算一次，而在后面需要時只要簡單查一下，從而避免大量的重復計算，最終得到多項式時間的算法 )(2 2nnn ???????????用動態(tài)規(guī)劃法求最優(yōu)解 public static void matrixChain(int [] p, int [][] m, int [][] s) { int n=。 for (int i = 1。 i = n。 i++) m[i][i] = 0。 for (int r = 2。 r = n。 r++) for (int i = 1。 i = n
教學課件相關推薦
鄂ICP備17016276號-1