第四章dynamicprogramming技術-資料下載頁

　　

【正文】 di的概率為 qi 問題的定義 k2 k4 d1 k1 d0 k3 k5 d2 d3 d4 d5 101?? ????njni jiqp搜索樹的期望代價 injiTiniiT qdD E PpkD E PTE )1)(()1)(()(01??? ?????HIT CSamp。E 169。DBLAB(2022) ?問題的定義 輸入 ： k={k1, k2, … , kn}, k1 k2 … kn, P={p1, p2, … , pn}, pi為搜索 ki的概率 Q={q0, q1, … , qn}, qi為搜索值 di的概率 輸出 ： K的二叉搜索樹 T, E(T)最小 HIT CSamp。E 169。DBLAB(2022) ? 優化子結構 定理 . 如果優化二叉搜索樹 T具有包含關鍵字集合 {ki, ki+1, … , kj}子樹 T’, 則 T’必是關于關鍵字 集合 {ki, ki+1, … , kj}子問題的優化解 . 證明 : 若不然 ， 必有關鍵字集 {ki, ki+1, … , kj}子樹 T’’， T’’的期望搜索代價低于 T’. 用 T’’替換 T中的 T’, 可以得到一個期望搜索代價 比 T小的原始問題的二叉搜索樹 , 與 T是最優解矛盾 . 優化二叉搜索樹結構的分析 HIT CSamp。E 169。DBLAB(2022) ? 用優化子結構從子問題優化解構造優化解 K={ki, ki+1, … , kj}的優化解的根必為 K中某個 kr kr ki, …, k r1 kr+1, …, k j 只要對于每個 kr?K, 確定 {ki , …, kr1}和 {kr+1, …, kj} 的優化解 , 我們就可以求出 K的優化解 . 如果 r=i, 左子樹 {ki, …, k i1}僅包含 di1 如果 r=j, 右子樹 {kr+1, …, kj }僅包含 dj HIT CSamp。E 169。DBLAB(2022) ? 令 E(i, j)為 {ki, … , kj}的優化解 Tij的期望搜索代價 –當 j=i1時 , Tij中只有葉結點 di1, E(i, i1)=qi1 –當 j?i時 , 選擇一個 kr?{ki, … , kj}: 建立優化解的搜索代價遞歸方程 kr ki, …, k r1 kr+1, …, k j 當把左右優化子樹放進 Tij時 , 每個結點的深度增加 1 E(i, j)=Pr + E(左子樹 )+ W(i, r1)+ E(右子樹 )+ W(r+1, j) HIT CSamp。E 169。DBLAB(2022) 由 lqldD E PlpkD E PLTEril 左ril 左l )2)(()2)(()1(111???? ?????????????????????111)()1()1,(rilril lqlpLTELTEriW 知 同理 , ????????jiljil lqlpjrW1),1(? 計算 W(i, r1)和 W(r+1, j) W(i, j)=W(i, r1) + W(r+1, j) + Pr lqldD E PlpkD E PLTEril 左ril 左l )1)(()1)(()(111??? ???????? E(i, j) = E(i, r1) + E(r+1, j) + W(i, j) HIT CSamp。E 169。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。E 169。DBLAB(2022) ? E(i, j)=mini?r?j {E(i,r1)+E(r+1,j)+W(i, j)} 自下而上計算優化解的搜索代價 E(1,4) E(1,0) E(2,4) E(1,1) E(3,4) E(1,2) E(4,4) E(1,3) E(5,4) E(2,1) E(2,2) E(2,3) E(3,3) E(3,2) E(4,3) q4 = q3 = q2 = q1 = q0 = HIT CSamp。E 169。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。E 169。DBLAB(2022) ?算法 ?數據結構 ? M[1:n+1。 0:n]: 存儲優化解搜索代價 ? W[1: n+1。 0:n]: 存儲代價增量 ? Root[1:n。 1:n]: root(i, j)記錄子問題 {ki, …, k j}優化解的根 HIT CSamp。E 169。DBLAB(2022) OptimalBST(p, q, n) For i=1 To n+1 Do E(i, i1) = qi1。 W(i, i1) = qi1。 For l=1 To n Do For i=1 To nl+1 Do j=i+l1。 E(i, j)=?。 W(i, j)=W(i, j1)+pj+qj。 For r=i To j Do t=E(i, r1)+E(r+1, j)+W(i, j)。 If tE(i, j) Then E(i, j)=t。 Root(i, j)=r。 Return E and Root HIT CSamp。E 169。DBLAB(2022) 作業：優化解的構造算法 HIT CSamp。E 169。DBLAB(2022) ? 時間復雜性 – (l, i, r)三層循環 ， 每層循環至多 n步 –時間復雜性為 O(n3) ? 空間復雜性 –二個 (n+1)?(n+1)數組 ， 一個 n?n數組 – O(n2) 算法的復雜性