【正文】 ?實(shí)現(xiàn)方法通常為自底向上的遞歸形式，但也可以采用自上而下的形式 (備忘錄方法 )。 ?基本思想是造表記錄已解的子問(wèn)題，再次遇到時(shí)僅查表即可，避免了重復(fù)計(jì)算，提高效率。 0:n]: 存儲(chǔ)子樹(shù)的概率和 ? s[1:n。 2021年 11月 12日 98 ?用優(yōu)化子結(jié)構(gòu)從子問(wèn)題優(yōu)化解構(gòu)造優(yōu)化解 Tij={xi, xi+1, … , xj}的優(yōu)化解的根必為 Tij中某個(gè) k xk xi, …, x k1 xk+1, , xj 只要對(duì)于每個(gè) xk? Tij , 確定 {xi , …, x k1}和 {xk+1, …, x j} 的優(yōu)化解 , 就可以求出 Tij的優(yōu)化解 . 如果 k=i, 左子樹(shù)僅包含 yi1 如果 k=j, 右子樹(shù)僅包含 yj 建立最優(yōu)解的搜索代價(jià)遞歸方程 2021年 11月 12日 99 建立最優(yōu)解的搜索代價(jià)遞歸方程 ?令 w(i, j)=ai1+bi+… +bj+aj ?令 m(i, j)為 {xi, …, xj}的最優(yōu)解 Tij的期望搜索代價(jià) ?當(dāng) j=i1時(shí) , m(i, i1)=0 ?當(dāng) j?i時(shí) , 假設(shè)以 xk?{xi, … , xj}為子樹(shù)根結(jié)點(diǎn)可得最優(yōu)二叉樹(shù) : xk xi, …, x k1 xk+1, …, x j 當(dāng)把左右最優(yōu)子樹(shù)放進(jìn) Tij時(shí) , 每個(gè)結(jié)點(diǎn)的深度增加 1 m(i, j)=bk + m(i, k1)+ W(i, k1)+ m(k+1, j)+ W(k+1, j) = W(i, j)+ m(i, k1)+ m(k+1, j) 2021年 11月 12日 100 建立最優(yōu)解的搜索代價(jià)遞歸方程 總之 m(i, j)=0 If j=i1 m(i, j)= W(i, j)+mini?k?j {m(i,k1)+m(k+1,j)} if j?i 2021年 11月 12日 101 自底向上計(jì)算最優(yōu)值 m(i, j)= W(i, j)+mini?k?j {m(i,k1)+m(k+1,j)} if j?i m(1,4) m(1,0) m(2,4) m(1,1) m(3,4) m(1,2) m(4,4) m(1,3) m(5,4) m(2,1) m(2,2) m(2,3) m(3,3) m(3,2) m(4,3) 0= 0 = 0 = 0 = 0= 2021年 11月 12日 102 自底向上計(jì)算最優(yōu)值 W(i, i1)=ai1； w(i, j)= W(i, j1)+bj+aj 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) a4 = a3 = a2 = a1 = a0 = 2021年 11月 12日 103 算法實(shí)現(xiàn) ?數(shù)據(jù)結(jié)構(gòu) ? m[1:n+1。 證明 : 若不然 ， 必有關(guān)鍵字集 {xi, xi+1, … ,xj}子樹(shù) T’’，T’’的期望搜索代價(jià)低于 T’。 2021年 11月 12日 93 問(wèn)題定義 ?二叉搜索樹(shù) T ?S={x1, x2, … , xn}，關(guān)鍵字 ?Y={y0, y1, … , yn}，虛擬鍵 ?yi對(duì)應(yīng)區(qū)間 (xi, xi+1) ?y0對(duì)應(yīng)區(qū)間 (?, x1) ?yn對(duì)應(yīng)區(qū)間 (xn,+?) ?搜索 xi的概率為 bi ?搜索 yi的概率為 ai x2 x4 y1 x1 y0 x3 x5 y2 y3 y4 y5 110?? ????njni jiba2021年 11月 12日 94 問(wèn)題定義 ?二叉搜索樹(shù)的平均路長(zhǎng)（期望代價(jià)）： ?????????????? ??njjdjaniicibyde pjaxde pibpnjjTniiT0)1(1)1()1)(()1)((01?其中， 是關(guān)鍵字 的結(jié)點(diǎn)深度； 是虛擬關(guān)鍵字 的結(jié)點(diǎn)深度。 )(n?)(C?)(nC?)(nC?)(nC?)(nC?)(C?2021年 11月 12日 91 提綱 一、動(dòng)態(tài)規(guī)劃算法的基本思想 二、矩陣連乘問(wèn)題 三、最長(zhǎng)公共子序列 四、最大子段和 五、 01背包問(wèn)題 六、最優(yōu)二叉搜索樹(shù) 2021年 11月 12日 92 問(wèn)題定義 ?二叉搜索樹(shù) The Optimal binary search trees 給定一個(gè)由 n個(gè)互異的關(guān)鍵字組成的序列 S={x1,x2,…x n}，并且關(guān)鍵字有序，即 x1x2…x n。 空間復(fù)雜性也是 。 0,0 ?? ji],[ jiV],1[ jiV ?ii vwjiV ??? ],1[iwj ?iwj ?2021年 11月 12日 87 因此得到如下遞推關(guān)系式： ???????????}],1[],1[m ax {],1[0],[ii vwjiVjiVjiVjiViiwjiwjji?????且若若或若0002021年 11月 12日 88 動(dòng)態(tài)規(guī)劃算法 算法 knapsack 輸入：重量分別為 ， 價(jià)值分別為 的物品 ， 背包的容量為 正整數(shù) C。 （ 2） ：用最優(yōu)的方法取自前 i1項(xiàng)的物品裝入容量為 的背包所得到的價(jià)值的最大值加上物品 i的價(jià)值。 ],[ jiVCjni ???? 0,0],0[ jV]0,[iV01背包另一種思路： ? ?v ,2021年 11月 12日 86 如果將背包的容量作為多階段決策 ， 當(dāng) 時(shí) ，有如下結(jié)論： 是下面兩個(gè)量的最大值 。 其中 ， 表示沒(méi)有東西裝入體積為 j的背包中； 而 表示沒(méi)有東西可以裝入體積為 0的背包中 。 ?可以對(duì) Knapsack算法進(jìn)行改進(jìn)，詳見(jiàn)課本。 2021年 11月 12日 84 算法復(fù)雜性分析 ?Knapsack的計(jì)算時(shí)間： O(nc)； ?Traceback的計(jì)算時(shí)間： O(n)； ?當(dāng)背包容量 c很大時(shí)，算法需要的計(jì)算時(shí)間較多。 m[1][10]=15 2021年 11月 12日 81 0 1 2 3 4 5 6 7 8 9 10 15 0 0 3 3 6 6 9 9 9 10 11 0 0 0 0 6 6 6 6 6 10 11 0 0 0 0 6 6 6 6 6 10 10 0 0 0 0 6 6 6 6 6 6 6 I=1 I=2 I=3 I=4 I=5 2021年 11月 12日 82 自底向上計(jì)算最優(yōu)值 計(jì)算 m(i, j)需要 m(i+1, jwi)和 m(i+1, j) 令 wi=整數(shù) , n=4 m(2,Cw1) m(1,C) m(2,C) m(4, 0) m(3, Cw1w2) m(3,Cw1) m(4,Cw2) m(4,Cw1) m(4,C) m(3,C) m(3,Cw2) … … … … … … … … … … … m(3, 0) m(2, 0) m(4, Cw1w2) … 2021年 11月 12日 83 1. m(1, C)是最優(yōu)解代價(jià)值，相應(yīng)解計(jì)算如下： If m(1, C)=m(2, C) Then x1=0 Else x1=1。 m[1][c]=m[2][c]。j++) m[i][j]=max(m[i+1][j],m[i+1][ jw[i] ]+v[i])。 for(int j=w[i]。j=jMax。i){ int jMax=min(w[i]1,c)。j++)進(jìn)行初始化： m[5][0]=0 m[5][1]=0 m[5][2]=0 m[5][3]=0 m[5][4]=6 ： ： m[5][10]=6 2021年 11月 12日 76 接著由循環(huán)體 for(int i=n1。j++)和 for(int j=w[n]。 } 2021年 11月 12日 75 假設(shè) w={2,2,6,5,4} v={6,3,5,4,6} 該程序按循環(huán)順序運(yùn)行的時(shí)候先是由語(yǔ)句 for(int j=0。c=w[i]。i++) if(m[i][c]==m[i+1][c]]) x[i]=0。 } 2021年 11月 12日 74 templateclass Type void Traceback(Type**m,int w,int c,int n,int x) { for(int i=1。 } m[1][c]=m[2][c]。j=c。j++) m[i][j]=m[i1][j]。 for(int j=0。i1。j++) m[n][j]=v[n]。 for(int j=w[n]。j=jMax。由 01背包問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計(jì)算 m(i， j)的遞歸式如下： iiiiwjwjjimvwjimjimjim????????????0),1(}),1(),1(m a x{),(nnnwjwjvjnm???????00),(2021年 11月 12日 73 templateclass Type void Knapsack(Type v,int w,int c,int n,Type**m) { int jMax=min(w[n]1,c)。于是 , (y1, z2, …, z n)是原問(wèn)題比 (y1, y2, …, y n)更優(yōu)解，矛盾。在對(duì) xi1決策后，已確定了(x1, …, xi1)，在決策 xi時(shí)，問(wèn)題處于下列兩種狀態(tài)之一： （ 1）背包容量不足以裝入物品 i，則 xi=0，背包不增加價(jià)值； （ 2）背包容量可以裝入物品 i，則 xi=1，背包的價(jià)值增加了 vi。 2021年 11月 12日 68 提綱 一、動(dòng)態(tài)規(guī)劃算法的基本思想 二、矩陣連乘問(wèn)題 三、最長(zhǎng)公共子序列 四、最大子段和 五、 01背包問(wèn)題 六、最優(yōu)二叉搜索樹(shù) 2021年 11月 12日 69 問(wèn)題定義 ?0/1 Knapsack Problem ? 給定 n種物品和一個(gè)背包，物品 i的重量是 wi，價(jià)值vi,背包容量為 C， 問(wèn)如何選擇裝入背包的物品，使裝入背包中的物品的總價(jià)值最大？ ?對(duì)于每種物品只能選擇完全裝入或不裝入，一個(gè)物品至多裝入一次。 2021年 11月 12日 66 提綱 一、動(dòng)態(tài)規(guī)劃算法的基本思想 二、矩陣連乘問(wèn)題 三、最長(zhǎng)公共子序列 四、最大子段和 五、 01背包問(wèn)題 六、最優(yōu)二叉搜索樹(shù) 2021年 11月 12日 67 最大子段和問(wèn)題 給定由 n個(gè)整數(shù)組成的序列 (a1, a2, … , an)， 求該序列形如 的子段和的最大值 ， 當(dāng)所有整數(shù)均為負(fù)整數(shù)時(shí) ， 其最大子段和為 0。因此，用 2行的數(shù)組空間就可以計(jì)算出最長(zhǎng)公共子序列的長(zhǎng)度。 ?如果只需要計(jì)算最長(zhǎng)公共子序列的長(zhǎng)度，則算法的空間需求可大大減少。事實(shí)上，數(shù)組元素 c[i][j]的值僅由 c[i1][j1]， c[i1][j]和c[i][j1]這 3個(gè)數(shù)組元素的值所確定。 } 2021年 11月 12日 62 找出最長(zhǎng)共同子序列 ?從 b[m, n]