算法與設(shè)計(jì)：動(dòng)態(tài)規(guī)劃法-資料下載頁(yè)
2025-08-07 11:24本頁(yè)面
【正文】 b,a,b, d, b,b)，建，建立兩個(gè)立兩個(gè) (m+1)(n+1)的二維表的二維表 L和表和表 S，分別存放搜索過程，分別存放搜索過程中得到的子序列的長(zhǎng)度和狀態(tài)。中得到的子序列的長(zhǎng)度和狀態(tài)。算法算法 ———— 最長(zhǎng)公共子序列問題最長(zhǎng)公共子序列問題intCommonOrder(intm,intn,intx[],inty[],intz[]){for(j=0。j=n。j++)//初始化第初始化第 0行行L[0][j]=0。for(i=0。j=m。i++)//初始化第初始化第 0列列L[i][0]=0。for(i=1。i=m。i++)for(j=1。j=n。j++)if(x[i]==y[j]){L[i][j]=L[i1][j1]+1。S[i][j]=1。}elseif(L[i][j1]=L[i1][j]){L[i][j]=L[i][j1]。S[i][j]=2。}else{L[i][j]=L[i1][j]。S[i][j]=3。}i=m。j=n。k=L[m][n]。for(i0amp。amp。j0){if(S[i][j]==1){z[k]=x[i]。k。i。j。}elseif(S[i][j]==2)j。elsei。}returnL[m][n]。}第一個(gè)第一個(gè) for循環(huán)的時(shí)間性能是循環(huán)的時(shí)間性能是 O(n)；；第二個(gè)第二個(gè) for循環(huán)的時(shí)間性能是循環(huán)的時(shí)間性能是 O(m)；；第三個(gè)循環(huán)是兩層嵌套的第三個(gè)循環(huán)是兩層嵌套的 for循環(huán)，其時(shí)間性能是循環(huán)，其時(shí)間性能是O(m n)；；第四個(gè)第四個(gè) for循環(huán)的時(shí)間性能是循環(huán)的時(shí)間性能是 O(k)，而，而 k≤≤ min{m,n}，所以，算法所以，算法 O(m n)。 返回返回 設(shè)設(shè) {r1,r2,…… ,rn}是是 n個(gè)記錄的集合，其查找概率分別是個(gè)記錄的集合，其查找概率分別是{p1,p2,…… ,pn}， 最優(yōu)二叉查找樹（最優(yōu)二叉查找樹（ Optimal Binary SearchTrees）） 是以這是以這 n個(gè)記錄構(gòu)成的二叉查找樹中具有最少平均個(gè)記錄構(gòu)成的二叉查找樹中具有最少平均比較次數(shù)的二叉查找樹，即比較次數(shù)的二叉查找樹，即 最小，其中最小，其中 pi是記錄是記錄 ri的查找概率，的查找概率， ci是在二叉查找樹中是在二叉查找樹中查找查找 ri的比較次數(shù)。的比較次數(shù)。 最優(yōu)二叉查找樹最優(yōu)二叉查找樹 查找問題中的動(dòng)態(tài)規(guī)劃法查找問題中的動(dòng)態(tài)規(guī)劃法 返回返回ABCD(a)(b)(c)二叉查找樹示例二叉查找樹示例BCDAABCD例如，集合例如，集合 {A,B,C,D}的查找概率是的查找概率是 {,,,}， (a)的平均比較次數(shù)是的平均比較次數(shù)是 1＋＋ 2+3+4=，(b)的平均比較次數(shù)是的平均比較次數(shù)是 2＋＋ 1+2+3=，(c)的平均比較次數(shù)是的平均比較次數(shù)是 3＋＋ 2+1+2=。將由將由 {r1,r2,…… ,rn}構(gòu)成的二叉查找樹記為構(gòu)成的二叉查找樹記為 T(1,n)， 其中其中 rk（（ 1≤≤ k≤≤ n））是是 T(1,n)的根結(jié)點(diǎn)，則其左子樹的根結(jié)點(diǎn)，則其左子樹 T(1,k1)由由 {r1,…… ,rk1}構(gòu)成，其右子構(gòu)成，其右子樹樹 T(k+1,n)由由 {rk+1,…… ,rn}構(gòu)成。構(gòu)成。證明最優(yōu)二叉查找樹滿足最優(yōu)性原理證明最優(yōu)二叉查找樹滿足最優(yōu)性原理rkT(1,n)以以 rk為根的二叉查找樹為根的二叉查找樹T(k+1,n)T(1,k1)若若 T(1,n)是最優(yōu)二叉查找樹，則其左是最優(yōu)二叉查找樹，則其左子樹子樹 T(1,k1)和右子樹和右子樹 T(k+1,n)也是也是最優(yōu)二叉查找樹，如若不然，假設(shè)最優(yōu)二叉查找樹，如若不然，假設(shè)T39。(1,k1)是比是比 T(1,k1)更優(yōu)的二叉查更優(yōu)的二叉查找樹，則找樹，則 T39。(1,k1)的平均比較次數(shù)小的平均比較次數(shù)小于于 T(1,k1)的平均比較次數(shù)，從而由的平均比較次數(shù)，從而由T39。(1,k1)、 rk和和 T(k+1,n)構(gòu)成的二叉構(gòu)成的二叉查找樹查找樹 T39。(1,n)的平均比較次數(shù)小于的平均比較次數(shù)小于T(1,n)的平均比較次數(shù)，這與的平均比較次數(shù)，這與 T(1,n)是最優(yōu)二叉查找樹的假設(shè)相矛盾。是最優(yōu)二叉查找樹的假設(shè)相矛盾。 設(shè)設(shè) T(i,j)是由記錄是由記錄 {ri,…… ,rj}(1≤≤ i≤≤ j≤≤ n)構(gòu)成的二叉查找構(gòu)成的二叉查找樹，樹， C(i,j)是這棵二叉查找樹的平均比較次數(shù)。雖然最后的是這棵二叉查找樹的平均比較次數(shù)。雖然最后的結(jié)果是結(jié)果是 C(1,n)， 但遵循動(dòng)態(tài)規(guī)劃法的求解方法但遵循動(dòng)態(tài)規(guī)劃法的求解方法 ,需要求出所有需要求出所有較小子問題較小子問題 C(i,j)的值，考慮從的值，考慮從 {ri,…… ,rj}中選擇一個(gè)記錄中選擇一個(gè)記錄 rk作作為二叉查找樹的根結(jié)點(diǎn)，可以得到如下關(guān)系：為二叉查找樹的根結(jié)點(diǎn)，可以得到如下關(guān)系： 因此，得到如下動(dòng)態(tài)規(guī)劃函數(shù)：因此，得到如下動(dòng)態(tài)規(guī)劃函數(shù)： C(i,i1)=0(1≤i≤n+1)（式（式 ））C(i,i)=pi (1≤i≤n)（式（式 ））C(i,j)=min{C(i,k1)+C(k+1,j)+}(1≤i≤j≤n,i≤k≤j)（式（式 ））設(shè)一個(gè)二維表設(shè)一個(gè)二維表 C[n+1][n+1]， 其中其中 C[i][j]表示二叉查找樹表示二叉查找樹 T(i,j)的平均比較次數(shù)。注意到在式的平均比較次數(shù)。注意到在式 ，當(dāng)中，當(dāng) k=1時(shí)，求時(shí)，求 C[i][j]需要用到需要用到 C[i][0]，當(dāng)，當(dāng) k=n時(shí)，求時(shí)，求 C[i][j]需要用到需要用到 C[n+1][j]， 所所以，二維表以，二維表 C[n+1][n+1]行下標(biāo)的范圍為行下標(biāo)的范圍為 1～～ n+1， 列下標(biāo)的列下標(biāo)的范圍為范圍為 0～～ n。為了在求出由為了在求出由 {r1,r2,…, rn}構(gòu)成的二叉查找樹的平均比構(gòu)成的二叉查找樹的平均比較次數(shù)的同時(shí)得到最優(yōu)二叉查找樹，設(shè)一個(gè)二維表較次數(shù)的同時(shí)得到最優(yōu)二叉查找樹，設(shè)一個(gè)二維表R[n+1][n+1]， 其下標(biāo)范圍與二維表其下標(biāo)范圍與二維表 C相同，相同， R[i][j]表示二叉表示二叉查找樹查找樹 T(i,j)的根結(jié)點(diǎn)的序號(hào)。的根結(jié)點(diǎn)的序號(hào)。 例如，集合例如，集合 {A,B,C,D}的查找概率是的查找概率是 {,,,}，二維表，二維表 C和和 R的初始情況如圖的初始情況如圖 。所示。 0 1 2 3 41 0 2 0 3 0 4 0 5 0 0 1 2 3 41 1 2 2 3 3 4 45 在二維表在二維表 C和和 R中只需計(jì)算主對(duì)角線以上的元素。中只需計(jì)算主對(duì)角線以上的元素。首先計(jì)算首先計(jì)算 C(1,2)：： 在前兩個(gè)記錄構(gòu)成的最優(yōu)二叉查找樹的根結(jié)點(diǎn)的序號(hào)是在前兩個(gè)記錄構(gòu)成的最優(yōu)二叉查找樹的根結(jié)點(diǎn)的序號(hào)是 2。按對(duì)角線逐條計(jì)算每一個(gè)按對(duì)角線逐條計(jì)算每一個(gè) C(i,j)和和 R(i,j)， 得到最終表。得到最終表。 0 1 2 3 41 0 2 0 3 0 4 0 5 0 0 1 2 3 41 1 2 3 32 2 3 33 3 34 45 (a) 二維表二維表 C(b)二維表二維表 R最終表的狀態(tài)最終表的狀態(tài)d=1d=2d=3d=1d=2d=3設(shè)設(shè) n個(gè)字符的查找概率存儲(chǔ)在數(shù)組個(gè)字符的查找概率存儲(chǔ)在數(shù)組 p[n]中，動(dòng)態(tài)規(guī)劃法求解中，動(dòng)態(tài)規(guī)劃法求解最優(yōu)二叉查找樹的算法如下：最優(yōu)二叉查找樹的算法如下：算法算法 ———— 最優(yōu)二叉查找樹最優(yōu)二叉查找樹doubleOptimalBST(intn,doublep[],doubleC[][],intR[][]){for(i=1。i=n。i++)//按式按式 {C[i][i1]=0。C[i][i]=p[i]。R[i][i]=i。}C[n+1][n]=0。for(d=1。dn。d++)//按對(duì)角線逐條計(jì)算按對(duì)角線逐條計(jì)算for(i=1。i=nd。i++){j=i+d。min=∞。mink=i。sum=0。for(k=i。k=j。k++){sum=sum+p[k]。if(C[i][k1]+C[k+1][j]min){min=C[i][k1]+C[k+1][j]。mink=k。}}C[i][j]=min+sum。R[i][j]=mink。}returnC[1][n]。}返回返
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1