動(dòng)態(tài)規(guī)劃ppt課件-展示頁(yè)
2024-11-12 18:12本頁(yè)面
【正文】 i = 1。 在計(jì)算過(guò)程中 , 保存已解決的子問(wèn)題答案。 s[i][j] = k。 k++) { int t = 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。 16 計(jì)算最優(yōu)值 void MatrixChain(int *p， int n， int **m， int **s) { for (int i = 1。 在計(jì)算過(guò)程中，保存已解決的子問(wèn)題答案。這也是該問(wèn)題可用動(dòng)態(tài)規(guī)劃算法求解的又一顯著特征。 13 設(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í)， 這里 Ai的維數(shù)是 Pi1 Pi 可以遞歸地定義 m[i,j]為： jki pppjkmkimjim 1],1[],[],[ ??????????????????? jipppjkmkimjijimjki }],1[],[{mi n0],[1jki 的位置只有 種 可能 k ij?建立遞歸關(guān)系 14 m[i][j]給出了最優(yōu)值，最優(yōu)斷開(kāi)位置為 k： 若將對(duì)應(yīng)于 m[i, j]的斷開(kāi)位置 k記為 s[i, j], 在計(jì)算出最優(yōu)值 m[i, j]后 ,可遞歸的由 s[i, j]構(gòu)造出相應(yīng)的最優(yōu)解 . jki pppjkmkimjim 1],1[],[],[ ?????建立遞歸關(guān)系 15 )(2 2nnn ???????????計(jì)算最優(yōu)值 對(duì)于 1≤i≤j≤n不同的有序?qū)?(i,j)對(duì)應(yīng)于不同的子問(wèn)題。 這種性質(zhì)稱為 最優(yōu)子結(jié)構(gòu)性質(zhì) 。 設(shè)這個(gè)計(jì)算次序在矩陣 Ak和 Ak+1之間將矩陣鏈斷開(kāi)，1≤kn，則其相應(yīng)完全加括號(hào)方式為(A1A2…A k)(Ak+1Ak+2…A n) 計(jì)算量： A[1:k]的計(jì)算量加上 A[k+1:n]的計(jì)算量，再加上 A[1:k]和 A[k+1:n]相乘的計(jì)算量 12 分析最優(yōu)解的結(jié)構(gòu) 特征：計(jì)算 A[1:n]的最優(yōu)次序所包含的計(jì)算矩陣子鏈 A[1:k]和 A[k+1:n]的次序也是最優(yōu)的。 11 矩陣連乘問(wèn)題 窮舉法 動(dòng)態(tài)規(guī)劃 將矩陣連乘積 AiAi+1…A j 簡(jiǎn)記為 A[i:j], 這里 i≤j。 由于每種加括號(hào)方式都可以分解為兩個(gè)子矩陣的加括號(hào)問(wèn)題：(A1...Ak)(Ak+1…An)可以得到關(guān)于 P(n)的遞推式如下： )/4()(11)()(1)( 2/311nnPnnknPkPnPnnk???????????? ???矩陣連乘問(wèn)題 給定 n個(gè)矩陣｛ A1,A2,… ,An｝，其中 Ai與 Ai+1是可乘的，i=1， 2… ， n1。這種計(jì)算次序可以用 加括號(hào) 的方式來(lái)確定。考察這 n個(gè)矩陣的連乘積 A1A2… An。 1~3是動(dòng)態(tài)規(guī)劃算法最基本的步驟 , 若需要最優(yōu)解 , 則必須執(zhí)行步驟 4 5 完全加括號(hào)的矩陣連乘積 完全加括號(hào)的矩陣連乘積可遞歸地定義為： 1. 單個(gè)矩陣是完全加括號(hào)的； 2. 矩陣連乘積 A是完全加括號(hào)的，則 A可表示為 2個(gè)完全加括號(hào)的矩陣連乘積 B和 C的乘積并加括號(hào)，即 A=(BC) 設(shè)有四個(gè)矩陣 A, B, C, D，總共有五種完全加括號(hào)的方式 : (A((BC)D)) (A(B(CD))) ((AB)(CD)) (((AB)C)D) ((A(BC)D)) 6 完全加括號(hào)的矩陣連乘積 設(shè)有四個(gè)矩陣 A, B, C, D，它們的維數(shù)分別是： A=50 10, B=10 40, C=40 30, D=30 5 矩陣 A和 B可乘的條件是 : 矩陣 A的列數(shù)等于矩陣 B的行數(shù) . 設(shè) A是 p q的矩陣 , B是 q r的矩陣 , 則乘積是 p r的矩陣 。 3. 以 自底向上 的方式計(jì)算出最優(yōu)值。 通過(guò)應(yīng)用范例學(xué)習(xí)動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)策略 4 動(dòng)態(tài)規(guī)劃基本步驟 1. 找出最優(yōu)解的 性質(zhì) ，并刻劃其結(jié)構(gòu)特征。第 3章 動(dòng)態(tài)規(guī)劃 3 (1) 矩陣連乘問(wèn)題； (2) 最長(zhǎng)公共子序列； (3) 最大子段和 。 (4) 凸多邊形最優(yōu)三角剖分； (5) 多邊形游戲； (6) 圖像壓縮； (7) 電路布線； (8) 流水作業(yè)調(diào)度； (9) 背包問(wèn)題； (10) 最優(yōu)二叉搜索樹(shù)。 2. 遞歸地定義 最優(yōu)值。 4. 根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造 最優(yōu)解 。計(jì)算量是 pqr. 上述 5種完全加括號(hào)方式的計(jì)算工作量為 : (A((BC)D)), (A(B(CD))), ((AB)(CD)), (((AB)C)D), ((A(BC)D)) 16000, 10500, 36000, 87500, 34500 BC: 10 40 30 = 12021, (BC)D: 10 30 5 = 1500, (A((BC)D)): 50 10 5 = 2500 7 示例 8 示例 9 矩陣連乘問(wèn)題 定義： 給定 n個(gè)矩陣 {A1,A2,… ,An}，其中 Ai與 Ai+1是可乘的，i=1,2,… n1。 由于矩陣乘法滿足 結(jié)合律 ，所以計(jì)算矩陣的連乘可以有許多 不同的 計(jì)算次序。 若一個(gè)矩陣連乘積的計(jì)算次序完全確定，也就是說(shuō)該連乘積已完全加括號(hào)，則可以依此次序反復(fù)調(diào)用 2個(gè)矩陣相乘的標(biāo)準(zhǔn)算法計(jì)算出矩陣連乘積 10 算法復(fù)雜度分析： 對(duì)于 n個(gè)矩陣的連乘積，設(shè)其不同的計(jì)算次序?yàn)?P(n)。如何確定計(jì)算矩陣連乘積的計(jì)算次序，使得依此次序計(jì)算矩陣連乘積需要的數(shù)乘次數(shù)最少？ 窮舉法： 列舉出所有可能的計(jì)算次序，并計(jì)算出每一種計(jì)算次序相應(yīng)需要的數(shù)乘次數(shù)，從中找出一種數(shù)乘次數(shù)最少的計(jì)算次序。 考察計(jì)算 A[i:n]的最優(yōu)計(jì)算次序。 矩陣連乘計(jì)算次序問(wèn)題的最優(yōu)解包含著其 子問(wèn)題 的最優(yōu)解。 問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問(wèn)題可用動(dòng)態(tài)規(guī)劃算法求解的顯著特征。因此，不同子問(wèn)題的個(gè)數(shù)最多只有 在遞歸計(jì)算時(shí)， 許多子問(wèn)題被重復(fù)計(jì)算多次 。 用動(dòng)態(tài)規(guī)劃算法解此問(wèn)題，可依據(jù)其遞歸式以自底向上的方式進(jìn)行計(jì)算。 每個(gè)子問(wèn)題只計(jì)算一次，在后面需要時(shí)只要簡(jiǎn)單查一下，從而避免大量的重復(fù)計(jì)算，最終得到多項(xiàng)式時(shí)間的算法。 i = n。 for (int r = 2。 r++) //變量 i的跨度 for (int i = 1。 i++) { int j=i+r1。 s[i][j] = i。 k j。 if (t m[i][j]) { m[i][j] = t。} } } } → ↓ r 17
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1