第3章動(dòng)態(tài)規(guī)劃-展示頁
2024-10-10 19:17本頁面
【正文】 m[i][k] + m[k+1][j] + p[i1]*p[k]*p[j]。 for (int k = i+1。 m[i][j] = m[i+1][j]+ p[i1]*p[i]*p[j]。 i = n r+1。 r = n。 i++) m[i][i] = 0。 for (int i = 1。在計(jì)算過程中，保存已解決的子問題答案。這也是該問題可用動(dòng)態(tài)規(guī)劃算法求解的又一顯著特征。 12 建立遞歸關(guān)系 ? 設(shè)計(jì)算 A[i:j]， 1≤i≤j≤n，所需要的最少數(shù)乘次數(shù)m[i,j]，則原問題的最優(yōu)值為 m[1,n] ? 當(dāng) i=j時(shí)， A[i:j]=Ai，因此， m[i,i]=0， i=1,2,…,n ? 當(dāng) ij時(shí)， ? 可以遞歸地定義 m[i,j]為： jki pppjkmkimjim 1],1[],[],[ ?????這里 的維數(shù)為 iA ii pp ??1?????????????? jipppjkmkimjijimjki }],1[],[{m i n0],[1jki 的位置只有 種 可能 k ij?13 計(jì)算最優(yōu)值 ? 對(duì)于 1≤i≤j≤n不同的有序?qū)?(i,j)對(duì)應(yīng)于不同的子問題。這種性質(zhì)稱為 最優(yōu)子結(jié)構(gòu)性質(zhì) 。設(shè)這個(gè)計(jì)算次序在矩陣 Ak和 Ak+1之間將矩陣鏈斷開， i≤kj，則其相應(yīng)完全 加括號(hào)方式為 ). . .)(. . .( 211 jkkkii AAAAAA ???計(jì)算量： A[i:k]的計(jì)算量加上 A[k+1:j]的計(jì)算量，再加上 A[i:k]和 A[k+1:j]相乘的計(jì)算量 11 分析最優(yōu)解的結(jié)構(gòu) ? 特征：計(jì)算 A[i:j]的最優(yōu)次序所包含的計(jì)算矩陣子鏈 A[i:k]和 A[k+1:j]的次序也是最優(yōu)的。 算法復(fù)雜度分析： 對(duì)于 n個(gè)矩陣的連乘積，設(shè)其不同的計(jì)算次序?yàn)?P(n)。如何確定計(jì)算矩陣連乘積的計(jì)算次序，使得依此次序計(jì)算矩陣連乘積需要的數(shù)乘次數(shù)最少。這種計(jì)算次序可以用加括號(hào)的方式來確定。 7 完全加括號(hào)的矩陣連乘積 （ 1）單個(gè)矩陣是完全加括號(hào)的； （ 2）矩陣連乘積 是完全加括號(hào)的，則 可 表示為 2個(gè)完全加括號(hào)的矩陣連乘積 和 的乘積并加括號(hào)，即 A AB C)(BCA ?DCBA , , ,1050 ??A 4010 ??B 3040 ??C 530 ??D)))((( DBCA)))((( DCAB )))((( DBCA)))((( CDBA )))((( CDAB16000, 10500, 36000, 87500, 34500 ? 完全加括號(hào)的矩陣連乘積可遞歸地定義為： ? 設(shè)有四個(gè)矩陣 ，它們的維數(shù)分別是： ? 總共有五中完全加括號(hào)的方式 8 矩陣連乘問題 ? 給定 n個(gè)矩陣 ， 其中 與 是可乘的， 。 ? 以自底向上的方式計(jì)算出最優(yōu)值。 算法總體思想 n = n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 n/2 T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) T(n/4) T(n) Those who cannot remember the past are doomed to repeat it. Gee Santayana, The life of Reason, Book I: Introduction and Reason in Common Sense (1905) 6 動(dòng)態(tài)規(guī)劃基本步驟 ? 找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。在用分治法求解時(shí)，有些子問題被重復(fù)計(jì)算了許多次。1 第 3章 動(dòng)態(tài)規(guī)劃 2 ? 動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個(gè)子問題 n T(n/2) T(n/2) T(n/2) T(n/2) T(n) = 3 算法總體思想 ? 動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個(gè)子問題 n T(n/2) T(n/2) T(n/2) T(n/2) T(n) = 4 ? 但是經(jīng)分解得到的子問題往往不是互相獨(dú)立的。不同子問題的數(shù)目常常只有多項(xiàng)式量級(jí)。 算法總體思想 n T(n) = n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) 5 ? 如果能夠保存已解決的子問題的答案，而在需要時(shí)再找出已求得的答案，就可以避免大量重復(fù)計(jì)算，從而得到多項(xiàng)式時(shí)間算法。 ? 遞歸地定義最優(yōu)值。 ? 根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解?？疾爝@ n個(gè)矩陣的連乘積 ? 由于矩陣乘法滿足結(jié)合律，所以計(jì)算矩陣的連乘可以有許多不同的計(jì)算次序。 ? 若一個(gè)矩陣連乘積的計(jì)算次序完全確定，也就是說該連乘積已完全加括號(hào)，則可以依此次序反復(fù)調(diào)用 2個(gè)矩陣相乘的標(biāo)準(zhǔn)算法計(jì)算出矩陣連乘積 },. . . ,{ 21 nAAA iA 1?iA1,...,2,1 ?? ninAAA ...219 矩陣連乘問題 給定 n個(gè)矩陣｛ A1,A2,…,An｝，其中 Ai與 Ai+1是可乘的，i=1,2 ,…,n1。 ?窮舉法 ：列舉出所有可能的計(jì)算次序，并計(jì)算出每一種計(jì)算次序相應(yīng)需要的數(shù)乘次數(shù)，從中找出一種數(shù)乘次數(shù)最少的計(jì)算次序。 由于每種加括號(hào)方式都可以分解為兩個(gè)子矩陣的加括號(hào)問題：(A1...Ak)(Ak+1…An)可以得到關(guān)于 P(n)的遞推式如下： )/4()(11)()( 1)( 2/311nnPnnknPkPnP nnk???????????? ???10 矩陣連乘問題 ?窮舉法 ?動(dòng)態(tài)規(guī)劃 將矩陣連乘積 簡(jiǎn)記為 A[i:j] ，這里 i≤j jii AAA ...1?考察計(jì)算 A[i:j]的最優(yōu)計(jì)算次序。 ? 矩陣連乘計(jì)算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動(dòng)態(tài)規(guī)劃算法求解的顯著特征。因此，不同子問題的個(gè)數(shù)最多只有 ? 由此可見，在遞歸計(jì)算時(shí)， 許多子問題被重復(fù)計(jì)算多次 。 ? 用動(dòng)態(tài)規(guī)劃算法解此問題，可依據(jù)其遞歸式以自底向上的方式進(jìn)行計(jì)算。每個(gè)子問題只計(jì)算一次，而在后面需要時(shí)只要簡(jiǎn)單查一下，從而避免大量的重復(fù)計(jì)算，最終得到多項(xiàng)式時(shí)間的算法 )(2 2nnn ???????????14 用動(dòng)態(tài)規(guī)劃法求最優(yōu)解 public static void matrixChain(int [] p, int [][] m, int [][] s) { int n=。 i = n。 for (int r = 2。 r++) for (int i = 1。 i++) { int j=i+r1。 s[i][j] = i。 k j。 if (t m[i][j]) { m[i][j] = t。} } } } A1 A2 A3 A4 A5 A6 30?35 35?15 15?5 5?10 10?20 20?25 ??????????????????????????????1 1 3 7 520223504 3 7 5]5][5[]4][2[7 1 2 5205351 0 0 02 6 2
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1