動(dòng)態(tài)規(guī)劃網(wǎng)絡(luò)ppt課件-展示頁(yè)
2025-05-15 12:09本頁(yè)面
【正文】 而在后面需要時(shí)只要簡(jiǎn)單查一下，從而避免大量的重復(fù)計(jì)算，最終得到多項(xiàng)式時(shí)間的算法 )(2 2nnn ???????????15 用動(dòng)態(tài)規(guī)劃法求最優(yōu)解 void MatrixChain(int *p， int n， int **m， int **s) { for (int i = 1。 ? 用動(dòng)態(tài)規(guī)劃算法解此問(wèn)題，可依據(jù)其遞歸式以自底向上的方式進(jìn)行計(jì)算。因此，不同子問(wèn)題的個(gè)數(shù)最多只有 ? 由此可見(jiàn)，在遞歸計(jì)算時(shí)， 許多子問(wèn)題被重復(fù)計(jì)算多次 。問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問(wèn)題可用動(dòng)態(tài)規(guī)劃算法求解的顯著特征。 ? 矩陣連乘計(jì)算次序問(wèn)題的最優(yōu)解包含著其子問(wèn)題的最優(yōu)解。 由于每種加括號(hào)方式都可以分解為兩個(gè)子矩陣的加括號(hào)問(wèn)題：(A1...Ak)(Ak+1…An)可以得到關(guān)于 P(n)的遞推式如下： )/4()(11)()(1)( 2/311nnPnnknPkPnPnnk???????????? ???11 矩陣連乘問(wèn)題 ?窮舉法 ?動(dòng)態(tài)規(guī)劃 將矩陣連乘積 簡(jiǎn)記為 A[i:j] ，這里 i≤j jii AAA ...1?考察計(jì)算 A[i:j]的最優(yōu)計(jì)算次序。 ?窮舉法 ：列舉出所有可能的計(jì)算次序，并計(jì)算出每一種計(jì)算次序相應(yīng)需要的數(shù)乘次數(shù)，從中找出一種數(shù)乘次數(shù)最少的計(jì)算次序。 ? 若一個(gè)矩陣連乘積的計(jì)算次序完全確定，也就是說(shuō)該連乘積已完全加括號(hào)，則可以依此次序反復(fù)調(diào)用 2個(gè)矩陣相乘的標(biāo)準(zhǔn)算法計(jì)算出矩陣連乘積 },. . . ,{ 21 nAAA iA 1?iA1,...,2,1 ?? ninAAA ...2110 矩陣連乘問(wèn)題 給定 n個(gè)矩陣｛ A1,A2,…,An｝，其中 Ai與 Ai+1是可乘的， i=1，2…， n1?？疾爝@ n個(gè)矩陣的連乘積 ? 由于矩陣乘法滿足結(jié)合律，所以計(jì)算矩陣的連乘可以有許多不同的計(jì)算次序。 8 ? 完全加括號(hào)的矩陣連乘積可遞歸地定義為： （ 1）單個(gè)矩陣是完全加括號(hào)的； （ 2）矩陣連乘積 A是完全加括號(hào)的，則 A可表示為 2個(gè)完全加括號(hào)的矩陣連乘積 B和 C的乘積并加括號(hào)，即 A=(BC) 。 ? 以自底向上的方式計(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) 7 動(dòng)態(tài)規(guī)劃基本步驟 ? 找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。在用分治法求解時(shí)，有些子問(wèn)題被重復(fù)計(jì)算了許多次。 4 ? 動(dòng)態(tài)規(guī)劃算法與分治法類(lèi)似，其基本思想也是將待求解問(wèn)題分解成若干個(gè)子問(wèn)題 算法總體思想 n T(n/2) T(n/2) T(n/2) T(n/2) T(n) = 5 ? 但是經(jīng)分解得到的子問(wèn)題往往不是互相獨(dú)立的。 3 ? 通過(guò)應(yīng)用范例學(xué)習(xí)動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)策略。 ? (3)以自底向上的方式計(jì)算出最優(yōu)值。 ? (1)找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。1 第 3章 動(dòng)態(tài)規(guī)劃 2 學(xué)習(xí)要點(diǎn) : ? 理解動(dòng)態(tài)規(guī)劃算法的概念。 ? 掌握動(dòng)態(tài)規(guī)劃算法的基本要素 ? （ 1）最優(yōu)子結(jié)構(gòu)性質(zhì) ? （ 2）重疊子問(wèn)題性質(zhì) ? 掌握設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法的步驟。 ? (2)遞歸地定義最優(yōu)值。 ? (4)根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。 ? （ 1）矩陣連乘問(wèn)題； ? （ 2）最長(zhǎng)公共子序列； ? （ 3）最大子段和 ? （ 4）凸多邊形最優(yōu)三角剖分； ? （ 5）多邊形游戲； ? （ 6）圖像壓縮； ? （ 7）電路布線； ? （ 8）流水作業(yè)調(diào)度； ? （ 9）背包問(wèn)題； ? （ 10）最優(yōu)二叉搜索樹(shù)。不同子問(wèn)題的數(shù)目常常只有多項(xiàng)式量級(jí)。 算法總體思想 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) 6 ? 如果能夠保存已解決的子問(wèn)題的答案，而在需要時(shí)再找出已求得的答案，就可以避免大量重復(fù)計(jì)算，從而得到多項(xiàng)式時(shí)間算法。 ? 遞歸地定義最優(yōu)值。 ? 根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。 ? 設(shè)有四個(gè)矩陣 A,B,C,D ，它們的維數(shù)分別是： A=50 10， B=10 40， C=40 30， D=30 5 總共有五中完全加括號(hào)的方式： (((AB)C)D)， (A((BC)D))， (A(B(CD)))， ((AB)(CD))，((A(BC))D) 計(jì)算量分別為 87500, 16000, 10500, 36000, 34500 完全加括號(hào)的矩陣連乘積 9 矩陣連乘問(wèn)題 ? 給定 n個(gè)矩陣 ， 其中 與 是可乘的， 。這種計(jì)算次序可以用加括號(hào)的方式來(lái)確定。如何確定計(jì)算矩陣連乘積的計(jì)算次序，使得依此次序計(jì)算矩陣連乘積需要的數(shù)乘次數(shù)最少。 算法復(fù)雜度分析： 對(duì)于 n個(gè)矩陣的連乘積，設(shè)其不同的計(jì)算次序?yàn)?P(n)。設(shè)這個(gè)計(jì)算次序在矩陣 Ak和 Ak+1之間將矩陣鏈斷開(kāi)， 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ì)算量 12 ? 特征：計(jì)算 A[i:j]的最優(yōu)次序所包含的計(jì)算矩陣子鏈 A[i:k]和 A[k+1:j]的次序也是最優(yōu)的。這種性質(zhì)稱(chēng)為 最優(yōu)子結(jié)構(gòu)性質(zhì) 。 分析最優(yōu)解的結(jié)構(gòu) 13 建立遞歸關(guān)系 ? 設(shè)計(jì)算 A[i:j]， 1≤i≤j≤n，所需要的最少數(shù)乘次數(shù) m[i,j]，則原問(wèn)題的最優(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?14 計(jì)算最優(yōu)值 ? 對(duì)于 1≤i≤j≤n不同的有序?qū)?(i,j)對(duì)應(yīng)于不同的子問(wèn)題。這也是該問(wèn)題可用動(dòng)態(tài)規(guī)劃算法求解的又一顯著特征。在計(jì)算過(guò)程中，保存已解決的子問(wè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 5]5][4[]3][2[1 3 0 0 02022352 5 0 00]5][3[]2][2[m i n]5][2[541531521pppmmpppmmpppmmm算法復(fù)雜度分析： 算法 matrixChain的主要計(jì)算量取決于算法中對(duì) r，i和 k的 3重循環(huán)。因此算法的計(jì)算時(shí)間上界為 O(n3)。 16 動(dòng)態(tài)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1