動態(tài)規(guī)劃ppt課件-資料下載頁
2025-01-12 09:18本頁面
【正文】 記為 T(1， n)。設(shè)定元素 sk作為該樹的根結(jié)點， 1≤k≤n。則二叉查找樹 T(1， n)的左子樹由實結(jié)點 {s1,…,s k1}和虛結(jié)點 e0,…,e k1組成，記為 T(1， k1)，而右子樹由實結(jié)點 {sk+1,…,s n}和虛結(jié)點 ek,…,e n組成，記為 T(k+1， n)。 ? 如果 T(1， n)是最優(yōu)二叉查找樹，則左子樹 T(1， k1)和右子樹T(k+1， n)也是最優(yōu)二叉查找樹。如若不然，假設(shè) T39。 (k+1， n)是比 T(k+1， n)更優(yōu)的二叉查找樹，則 T39。 (k+1， n)的平均比較次數(shù)小于 T(k+1， n)的平均比較次數(shù)，從而由 T(1， k1)、 sk和 T39。 (k+1，n)構(gòu)成的二叉查找樹 T39。 (1， n)的平均比較次數(shù)小于 T(1， n)的平均比較次數(shù)，這與 T(1， n)是最優(yōu)二叉樹的前提相矛盾。因此，最優(yōu)二叉查找樹具有最優(yōu)子結(jié)構(gòu)性質(zhì)得證。 建立最優(yōu)值的遞歸關(guān)系式 ? (421) ? 其中 （ 422） ? 初始時， C(i， i1)=0。 wi(i1)=qi1 ，其中 1≤i≤n。 (423) ? 式（ 421）和（ 423）即為建立的最優(yōu)值遞歸定義式。 j )}1,C (k1)k{ C (i ,m i nj)w ( i ,j)C (i , jki ????? ??jj qp1)jw ( i ,j)w ( i , ????算法設(shè)計 ? 步驟 1：設(shè)計合適的數(shù)據(jù)結(jié)構(gòu)。設(shè)有序序列 S={s1,…,sn} ，數(shù)組s[n]存儲序列 S中的元素；數(shù)組 p[n]存儲序列 S中相應元素的查找概率；二維數(shù)組 C[n+1][n+1]，其中 C[i][j]表示二叉查找樹 T(i， j)的平均比較次數(shù)；二維數(shù)組 R[n+1][n+1]，其中 R[i][j]表示二叉查找樹 T(i， j)中作為根結(jié)點的元素在序列 S中的位置。數(shù)組 q[n]存儲虛結(jié)點 e0,e1…,e n的查找概率。為了提高效率，不是每次計算 C(i，j)時都計算 wij的值，而是把這些值存儲在二維數(shù)組 W[i][j]中； ? 步驟 2：初始化。設(shè)置 C[i][i1]=0； W[i][i1]=qi1； ? 步驟 3：循環(huán)階段。采用自底向上的方式逐步構(gòu)造最優(yōu)二叉查找樹； ? 步驟 31：字符集規(guī)模為 1的時候，即 Sij={si}， i=1,2, …,n 且 j=i，顯然這種規(guī)模的子問題有 n個，即首先要構(gòu)造出 n棵最優(yōu)二叉查找樹 T(1， 1)， T(2， 2),…,T(n ， n)。依據(jù)公式 (420)~(422)，很容易求得 W[i][i]和 C[i][i]。同時，對于所構(gòu)造的 n棵最優(yōu)二叉查找樹，它們的根分別記為： R[1][1]=1， R[2][2]=2,…,R[n][n]=n ； ? 依此類推，構(gòu)造出字符集 Sij中含 3個字符的最優(yōu)二叉查找樹、含 4個字符的最優(yōu)二叉查找樹，直到 …… ? 步驟 3n: 字符集規(guī)模為 n的時候，即 S1n={s1,s2,…,s n}，顯然這種規(guī)模的子問題有 1個，即要構(gòu)造出 1棵最優(yōu)二叉查找樹 T(1， n)。依據(jù)公式(421)，求得 W[i][j]，然后在整數(shù) 1,2…n 中選擇適當?shù)?k值，使得成立。同時，記錄該樹的根 R[1][n]=k； ? 步驟 4：最優(yōu)解的構(gòu)造。 ? 從 R[i][j]中保存的最優(yōu)二叉查找子樹 T(i， j)的根結(jié)點信息，可構(gòu)造出問題的最優(yōu)解。當 R[1][n]=k時，則元素 sk即為所求的最優(yōu)二叉查找樹的根結(jié)點。此時，需要計算兩個子問題：求左子樹 T(1， k1)和右子樹T(k+1， n)的根結(jié)點信息。如果 R[1][k1]=i，則元素 si即為 T(1， k1)的根結(jié)點元素。依此類推，將很容易由 R中記錄的信息構(gòu)造出問題的最優(yōu)解。 構(gòu)造實例 ? 【 例 411】 設(shè) 5個有序元素的集合為 {s1,s2,s3,s4,s5},查找概率p=p1,p2,p3,p4,p5= ,；葉結(jié)點元素{e0,e1,e2,e3,e4,e5}，查找概率 q=q0,q1,q2,q3,q4,q5= ,,。試構(gòu)造 5個有序元素的最優(yōu)二叉查找樹。 i1230 12j4563450 . 0 50 . 10 . 0 50 . 0 50 . 0 50 . 10 . 30 . 2 50 . 1 50 . 2 00 . 3 50 . 4 50 . 3 50 . 30 . 50 . 5 50 . 50 . 60 . 70 . 81 . 0Wi1230 12j4563450000000 . 30 . 2 50 . 1 50 . 2 00 . 3 50 . 70 . 50 . 4 50 . 71 . 00 . 9 51 . 0 51 . 4 51 . 6 52 . 3 5Ci1230 12j45345123451245225242R根據(jù) R中的信息構(gòu)造最優(yōu)解 ? 步驟 1：由于 R[1][5]=2，即 k=2，最優(yōu)二叉查找樹 T(1， 5)的根結(jié)點為 s2； ? 步驟 2：求出 T(1， 5)的左子樹 T(1， k1)=T(1， 1)的根結(jié)點為 s1； ? 步驟 3：求出 T(1， 5)的右子樹 T(k+1， 5)=T(3， 5)的根結(jié)點為 s5； ? 步驟 4：求出子樹 T(3， 5)的左子樹 T(3， 4)的根結(jié)點為 s4； ? 由此構(gòu)造出如圖 49所示的最優(yōu)二叉查找樹 s5s2s1e0e1e2e5s4s3e3e4算法分析 ? 由算法描述容易看出，語句 if((C[i][k1]+C[k+1][j])＜ C[i][j])對算法的運行時間貢獻最大，因此，可選該語句作為基本語句。對于固定的 t值，該語句需要的計算時間為O(ji)=O(t)，因此，它總的運行時間為 1 301( ) ( )n n ttiO t O n???????
教學課件相關(guān)推薦
鄂ICP備17016276號-1