第四章dynamicprogramming技術(shù)-預(yù)覽頁
【正文】 mp。DBLAB(2022) ?子問題重疊性 LCSXY LCSXm1Yn1 LCSXm1Y LCSXYn1 LCSXm2Yn2 LCSXm2Yn1 LCSXm1Yn2 …… LCS問題具有子問題重疊性 HIT CSamp。DBLAB(2022) ? 基本思想 自底向上計(jì)算 LCS的長(zhǎng)度 C[i1, j1] C[i1,j] C[i, j1] C[i, j] HIT CSamp。DBLAB(2022) ?計(jì)算 LCS長(zhǎng)度的算法 – 數(shù)據(jù)結(jié)構(gòu) C[0:m,0:n]: C[i,j]是 Xi與 Yj的 LCS的長(zhǎng)度 B[1:m,1:n]: B[i,j]是指針 ， 指向計(jì)算 C[i,j] 時(shí)所選擇的子問題的優(yōu)化解 所對(duì)應(yīng)的 C表的表 項(xiàng) HIT CSamp。 For i?1 To m Do For j?1 To n Do If xi = yj Then C[i,j]?C[i1,j1]+1； B[i,j]?“↖ ”。 B[i,j]?“←”。E 169。 ELSE If B[i, j]=“↑” THEN PrintLCS(B, X, i1, j)。DBLAB(2022) ?時(shí)間復(fù)雜性 – 計(jì)算代價(jià)的時(shí)間 ? (i, j)兩 層循環(huán) ,i循環(huán) m步 , j循環(huán) n步 ? O(mn) –構(gòu)造最優(yōu)解的時(shí)間 : O(m+n) –總時(shí)間復(fù)雜性為： O(mn) ?空降復(fù)雜性 – 使用數(shù)組 C和 B –需要空間 O(mn) 算法復(fù)雜性 HIT CSamp。DBLAB(2022) ?多邊形 多邊形表示為頂點(diǎn)坐標(biāo)集 P=(v0,v1,...vn)或頂點(diǎn)序列v0v1,...vn1vn ?簡(jiǎn)單多邊形 除了頂點(diǎn)以外沒有任何邊交叉點(diǎn)的多邊形 ?多邊形的內(nèi)部 、 邊界與外部 – 平面上由多邊形封閉的點(diǎn)集合稱為多邊形 內(nèi)部 ， – 多邊形上的點(diǎn)集合稱為多邊形的 邊界 – 平面上除多邊形內(nèi)部和邊界以外的點(diǎn)集合稱為多邊形的 外部 問題的定義 HIT CSamp。DBLAB(2022) ? 設(shè) – P=(v0,v1,...vn)是 n+1個(gè)頂 點(diǎn)的多邊形 – TP是 P的優(yōu)化三角剖分 ， 包含三角形 v0vk vn 優(yōu)化解結(jié)構(gòu)的分析 – TP=T(v0, ..., vk)∪ T(vk, ..., vn)∪ {v0vk, vkvn} V0 V1 V2 Vk Vk+1 Vk+2 Vn HIT CSamp。DBLAB(2022) 與矩陣鏈乘法問題一致 ， 把算法 MatrixchainOrder PrintOptimalParens 略加修改即可計(jì)算 t[i,j]并構(gòu)造優(yōu)化三角剖分解 優(yōu)化三角剖分動(dòng)態(tài)編程算法 HIT CSamp。DBLAB(2022) 問題的定義 給定 n種物品和一個(gè)背包，物品 i的重量是 wi，價(jià)值 vi, 背包容量為 C, 問如何選擇裝入背包的物品，使裝入背包中的物品的總價(jià)值最大？ 對(duì)于每種物品只能選擇完全裝入或不裝入，一個(gè)物品至多裝入一次。E 169。E 169。E 169。 For j=wn To C Do m[n, j] = vn。 Else m[1, C]=max{m[2, C], m[2, Cw1]+v1}。 2. 如果 x1=0, 由 m(2, C)繼續(xù)構(gòu)造最優(yōu)解； 3. 如果 x1=1, 由 m(2, Cw1)繼續(xù)構(gòu)造最優(yōu)解 . HIT CSamp。DBLAB(2022) ? 二叉搜索樹 T –結(jié)點(diǎn) ? K={k1, k2, … , kn} ? D={d0, d1, … , dn} ? di對(duì)應(yīng)區(qū)間 (ki, ki+1) d0對(duì)應(yīng)區(qū)間 (?, k1) dn對(duì)應(yīng)區(qū)間 (kn,+?) –附加信息 ? 搜索 ki的概率為 pi ? 搜索 di的概率為 qi 問題的定義 k2 k4 d1 k1 d0 k3 k5 d2 d3 d4 d5 101?? ????njni jiqp搜索樹的期望代價(jià) injiTiniiT qdD E PpkD E PTE )1)(()1)(()(01??? ?????HIT CSamp。DBLAB(2022) ? 優(yōu)化子結(jié)構(gòu) 定理 . 如果優(yōu)化二叉搜索樹 T具有包含關(guān)鍵字集合 {ki, ki+1, … , kj}子樹 T’, 則 T’必是關(guān)于關(guān)鍵字 集合 {ki, ki+1, … , kj}子問題的優(yōu)化解 . 證明 : 若不然 ， 必有關(guān)鍵字集 {ki, ki+1, … , kj}子樹 T’’， T’’的期望搜索代價(jià)低于 T’. 用 T’’替換 T中的 T’, 可以得到一個(gè)期望搜索代價(jià) 比 T小的原始問題的二叉搜索樹 , 與 T是最優(yōu)解矛盾 . 優(yōu)化二叉搜索樹結(jié)構(gòu)的分析 HIT CSamp。DBLAB(2022) ? 令 E(i, j)為 {ki, … , kj}的優(yōu)化解 Tij的期望搜索代價(jià) –當(dāng) j=i1時(shí) , Tij中只有葉結(jié)點(diǎn) di1, E(i, i1)=qi1 –當(dāng) j?i時(shí) , 選擇一個(gè) kr?{ki, … , kj}: 建立優(yōu)化解的搜索代價(jià)遞歸方程 kr ki, …, k r1 kr+1, …, k j 當(dāng)把左右優(yōu)化子樹放進(jìn) Tij時(shí) , 每個(gè)結(jié)點(diǎn)的深度增加 1 E(i, j)=Pr + E(左子樹 )+ W(i, r1)+ E(右子樹 )+ W(r+1, j) HIT CSamp。DBLAB(2022) 總之 E(i, j)=qi1 If j=i1 E(i, j)=mini?r?j {E(i,r1)+E(r+1,j)+W(i, j)} if j?i HIT CSamp。DBLAB(2022) ? W(i, i1) = qi1, W(i, j) = W(i, j1) + pj + qj W(1,4) W(1,0) W(2,4) W(1,1) W(3,4) W(1,2) W(4,4) W(1,3) W(5,4) W(2,1) W(2,2) W(2,3) W(3,3) W(3,2) W(4,3) q4 = q3 = q2 = q1 = q0 = HIT CSamp。 0:n]: 存儲(chǔ)代價(jià)增量 ? Root[1:n。 W(i, i1) = qi1。 For r=i To j Do t=E(i, r1)+E(r+1, j)+W(i, j)。E 1
法律信息相關(guān)推薦
鄂ICP備17016276號(hào)-1