動(dòng)態(tài)規(guī)劃ppt課件(參考版)
2025-01-15 09:18本頁(yè)面
【正文】 對(duì)于固定的 t值，該語(yǔ)句需要的計(jì)算時(shí)間為O(ji)=O(t)，因此，它總的運(yùn)行時(shí)間為 1 301( ) ( )n n ttiO t O n???????。試構(gòu)造 5個(gè)有序元素的最優(yōu)二叉查找樹(shù)。依此類(lèi)推，將很容易由 R中記錄的信息構(gòu)造出問(wèn)題的最優(yōu)解。此時(shí)，需要計(jì)算兩個(gè)子問(wèn)題：求左子樹(shù) T(1， k1)和右子樹(shù)T(k+1， n)的根結(jié)點(diǎn)信息。 ? 從 R[i][j]中保存的最優(yōu)二叉查找子樹(shù) T(i， j)的根結(jié)點(diǎn)信息，可構(gòu)造出問(wèn)題的最優(yōu)解。依據(jù)公式(421)，求得 W[i][j]，然后在整數(shù) 1,2…n 中選擇適當(dāng)?shù)?k值，使得成立。依據(jù)公式 (420)~(422)，很容易求得 W[i][i]和 C[i][i]。設(shè)置 C[i][i1]=0； W[i][i1]=qi1； ? 步驟 3：循環(huán)階段。數(shù)組 q[n]存儲(chǔ)虛結(jié)點(diǎn) e0,e1…,e n的查找概率。 j )}1,C (k1)k{ C (i ,m i nj)w ( i ,j)C (i , jki ????? ??jj qp1)jw ( i ,j)w ( i , ????算法設(shè)計(jì) ? 步驟 1：設(shè)計(jì)合適的數(shù)據(jù)結(jié)構(gòu)。 wi(i1)=qi1 ，其中 1≤i≤n。因此，最優(yōu)二叉查找樹(shù)具有最優(yōu)子結(jié)構(gòu)性質(zhì)得證。 (k+1，n)構(gòu)成的二叉查找樹(shù) T39。 (k+1， n)是比 T(k+1， n)更優(yōu)的二叉查找樹(shù)，則 T39。 ? 如果 T(1， n)是最優(yōu)二叉查找樹(shù)，則左子樹(shù) T(1， k1)和右子樹(shù)T(k+1， n)也是最優(yōu)二叉查找樹(shù)。設(shè)定元素 sk作為該樹(shù)的根結(jié)點(diǎn)， 1≤k≤n。 ? 注意：在查找概率不等的情況下，最優(yōu)二叉樹(shù)并不一定是高度最小的二叉查找樹(shù)。 ? （ d）由此可得，在遞歸地由 p[i1]計(jì)算 p[i]時(shí)，可先由 p[i1]計(jì)算出 q[i1]，然后合并 p[i1]和 q[i1]，并清除其中的受控跳躍點(diǎn)得到 p[i]。 ? （ b） p[i]可通過(guò)計(jì)算 p[i1]得到。 p[i]中的全部跳躍點(diǎn) (j， C[i][j])按 j升序排列。 改進(jìn)步驟 ? （ a）對(duì)每一個(gè)確定的 i，用一個(gè)表 p[i]來(lái)存儲(chǔ)函數(shù) C[i][j]的全部跳躍點(diǎn)。跳躍點(diǎn)是這一類(lèi)函數(shù)的描述特征。因此，在這里設(shè)計(jì)了對(duì)算法 KnapSack的改進(jìn)方法，采用該方法可克服這兩大缺點(diǎn)。 算法分析 ? 在算法 KnapSack中，第 3個(gè)循環(huán)是兩層嵌套的 for循環(huán)，為此，可選定語(yǔ)句 if(jw[i])作為基本語(yǔ)句，其運(yùn)行時(shí)間為n*W，由此可見(jiàn)，算法 KnapSack的時(shí)間復(fù)雜性為 O(nW)。由于 C[1][j]=C[1][4]=6C[0][4]=0，說(shuō)明物品 1被裝入了背包，因此 x1=1，且更新 j=jw[1]=42=2。由于 C[4][j]=C[4][6]=9=C[3][6]，說(shuō)明物品 4沒(méi)有被裝入背包，因此 x4 =0；由于C[3][j]=C[3][6]=9=C[2][6]=9，說(shuō)明物品 3沒(méi)有被裝入背包，因此 x3=0。 ? 如果 C[i][j]=C[i1][j]，說(shuō)明第 i個(gè)物品沒(méi)有被裝入背包，則 xi =0； ? 如果 C[i][j]C[i1][j]，說(shuō)明第 i個(gè)物品被裝入背包，則 xi =1， j=jwi。 ? 行 i表示物品 ， 列 j表示背包容量 ， 表中數(shù)據(jù)表示 C[i][j] 0 1 2 3 4 5 6 7 8 9 10 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 6 6 6 6 6 6 6 6 6 2 0 0 6 6 9 9 9 9 9 9 9 3 0 0 6 6 9 9 9 9 11 11 14 4 0 0 6 6 9 9 9 10 11 13 14 5 0 0 6 6 9 9 12 12 15 15 15 確定裝入背包的具體物品 ? 從 C[n][W]的值根據(jù)式（ 412）向前推，最終可求出裝入背包的具體物品，即問(wèn)題的最優(yōu)解。 ????????????1][ j ]C[iC[ i ][ j ]wjj,1x1][ j ]C[iC[ i ][ j ]jj,0xiii當(dāng)當(dāng)構(gòu)造實(shí)例 ? 【 例 48】 有 5個(gè)物品 ， 其重量分別為 2,2,6,5,4， 價(jià)值分別為 6,3,5,4,6。依此類(lèi)推，直到確定第 1個(gè)物品是否被裝入背包中為止。按式（ 411）確定前 i個(gè)物品能夠裝入背包的情況下得到的最優(yōu)值； ? 步驟 31： i=1時(shí)，求出 C[1][j]， 1≤j≤W； ? 步驟 32： i=2時(shí)，求出 C[2][j]， 1≤j≤W； ? 依此類(lèi)推，直到 …… ? 步驟 3n： i=n時(shí)，求出 C[n][W]。采用數(shù)組 w[n]來(lái)存放n個(gè)物品的重量；數(shù)組 v[n]來(lái)存放 n個(gè)物品的價(jià)值，背包容量為 W，數(shù)組 C[n+1][W+1]來(lái)存放每一次迭代的執(zhí)行結(jié)果；數(shù)組 x[n]用來(lái)存儲(chǔ)所裝入背包的物品狀態(tài)； ? 步驟 2：初始化。如何選取物品裝入背包，使背包中所裝入的物品的總價(jià)值最大？ ? 約束條件： （ 47） ? 目標(biāo)函數(shù)： （ 48） ? 于是，問(wèn)題歸結(jié)為尋找一個(gè)滿足約束條件（ 47），并使目標(biāo)函數(shù)（ 48）達(dá)到最大的解向量 X=(x1, x2,…, xn) 。 01背包問(wèn)題 ? 問(wèn)題描述 ? 01背包問(wèn)題可描述為： n個(gè)物品和 1個(gè)背包。 }t,m i n { t}t,m i n { t 1)2 P ( i1 P ( i )2 P ( i )1)1 P ( i ?? ?}t,m i n { t}t,m i n { t 2 P ( j )1 P ( i )2 P ( i )1 P ( j ) ?算法設(shè)計(jì) ? 步驟 1：令 N1={i|t1it2i},N2={i|t1it2i}； ? 步驟 2：將 N1中工件按 t1i非減序排序；將 N2中工件按 t2i非增序排序； ? 步驟 3： N1中工件接 N2中工件，即 N1N2就是所求的滿足 Johnson Bellman39。設(shè)最優(yōu)加工順序?yàn)?P，則 P的任意相鄰的兩個(gè)加工工件 P(i)和 P(i+1)滿足 ? 進(jìn)一步可以證明，最優(yōu)加工順序的第 i個(gè)和第 j個(gè)要加工的工件，如果 ij，則 ? 即：滿足 Johnson Bellman39。 建立最優(yōu)值的遞歸關(guān)系式 ? 設(shè) T(S， t)表
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1