1、 0020算法筆記【動態規劃】最優二叉搜索樹問題標簽： 最優二叉搜索樹算法筆記最小平均路長四邊形不等式動態規劃2013-03-20 10:37 10325人閱讀 評論(4) 收藏 舉報本文章已收錄于：  算法與數據結構知識庫 分類：算法（49） 版權聲明：本文為博主原創文章，未經博主允許不得轉載。      1、問題描速：       設 S=x1, x2, ···, xn 是

2、一個有序集合，且x1, x2, ···, xn表示有序集合的二叉搜索樹利用二叉樹的頂點存儲有序集中的元素，而且具有性質：存儲于每個頂點中的元素x 大于其左子樹中任一個頂點中存儲的元素，小于其右子樹中任意頂點中存儲的元素。二叉樹中的葉頂點是形如(xi, xi+1) 的開區間。在表示S的二叉搜索樹中搜索一個元素x，返回的結果有兩種情形：    (1) 在二叉樹的內部頂點處找到： x = xi    (2) 在二叉樹的葉頂點中確定： x (xi , xi+1)    設在情形(1)中找到元素x = x

3、i的概率為bi；在情形(2)中確定x (xi , xi+1)的概率為ai。其中約定x0= , xn+1= + ,有        集合a0,b1,a1,bn,an稱為集合S的存取概率分布。       最優二叉搜索樹：在一個表示S的二叉樹T中，設存儲元素xi的結點深度為ci；葉結點（xj，xj1）的結點深度為dj。         注：在檢索過程中，每進行一次比較，就進入下面一層，對于成功的檢索，比較的次數就是所在的層數加1。

4、對于不成功的檢索，被檢索的關鍵碼屬于那個外部結點代表的可能關鍵碼集合，比較次數就等于此外部結點的層數。對于圖的內結點而言，第0層需要比較操作次數為1，第1層需要比較2次，第2層需要3次。     p表示在二叉搜索樹T中作一次搜索所需的平均比較次數。P又稱為二叉搜索樹T的平均路長，在一般情況下，不同的二叉搜索樹的平均路長是不同的。對于有序集S及其存取概率分布(a0,b1,a1,bn,an)，在所有表示有序集S的二叉搜索樹中找出一棵具有最小平均路長的二叉搜索樹。         設Pi是對ai檢索的概率。設q

5、i是對滿足ai<X<ai+1,0<=i<=n的標識符X檢索的概率， (假定a0=-且an+1=+ )。      對于有n個關鍵碼的集合，其關鍵碼有n!種不同的排列，可構成的不同二叉搜索樹有棵。(n個結點的不同二叉樹,卡塔蘭數)。如何評價這些二叉搜索樹，可以用樹的搜索效率來衡量。例如：標識符集1, 2, 3do, if, stop可能的二分檢索樹為：     若P1=0.5, P2=0.1, P3=0.05,q0=0.15, q1=0.1, q2=0.05, q3=0.05，求每棵樹的平均比較次數（成

6、本）。          Pa(n)=1 × p1 + 2 × p2+3 × p3 + 1×q0 +2×q1+ 3×( q2 + q3 ) =1 × 0.5+ 2 × 0.1+3 ×0.05 + 1×0.05 +2×0.1+ 3×( 0.05 + 0.05 ) =1.5     Pb(n)=1 × p1 + 2 × p3+3 × p2 +

7、 1×q0 +2×q3 + 3×( q1 + q2 ) =1 × 0.5+ 2 × 0.05 + 3 ×0.1 + 1×0.15 +2×0.05+ 3×( 0.1 + 0.05 ) =1.6     Pc(n)=1 × p2 + 2 × (p1 +  p3) + 2×(q0 +q1 +q2 + q3 ) =1 × 0.1+ 2 × (0.5 + 0.05) + 2×(

8、0.15 + 0.1 + 0.05 + 0.05) =1.9     Pd(n)=1 × p3 + 2 × p1+3 × p2 + 1 × q3+2 × q0 +3 × (q1+ q2) =1 × 0.05 + 2 × 0.5 + 3 × 0.1 + 1×0.05 + 2 × 0.15 + 3 × (0.1 + 0.05) =2.15     Pe(n)=1 × p3 + 2

9、× p2+3 × p1 + 1 × q3+2 × q2 +3 × (q0 + q1) =1 × 0.05 + 2 × 0.1+ 3 × 0.5 + 1×0.05 + 2 × 0.15 + 3 × (0.15 + 0.1) =2.85     因此，上例中的最小平均路長為Pa(n)=1.5。     可以得出結論：結點在二叉搜索樹中的層次越深，需要比較的次數就越多，因此要構造一棵最小二叉樹，一般盡量把搜索概率

10、較高的結點放在較高的層次。     2、最優子結構性質：     假設選擇 k為樹根，則 1, 2, , k-1 和a0, a1, , ak-1 都將位于左子樹 L 上，其余結點 (k+1, , n 和 ak, ak+1, , an)位于右子樹 R 上。設COST(L) 和COST(R) 分別是二分檢索樹T的左子樹和右子樹的成本。則檢索樹T的成本是：P(k)+ COST(L) + COST(R) + 。若 T 是最優的，則上式及 COST(L) 和COST(R) 必定都取最小值。    證明：二

11、叉搜索樹T 的一棵含有頂點xi , ··· , xj和葉頂點(xi-1 , xi ) , ··· , ( xj , xj+1)的子樹可以看作是有序集 xi , ··· , xj關于全集為 xi-1 , xj+1 的一棵二叉搜索樹(T自身可以看作是有序集) 。根據S 的存取分布概率，在子樹的頂點處被搜索到的概率是：。xi , ··· , xj的存儲概率分布為ai-1, bi, , bj, aj

12、60;，其中，ah，bk分別是下面的條件概率：。     設Tij是有序集xi , ··· , xj關于存儲概率分布為ai-1, bi, , bj, aj的一棵最優二叉搜索樹，其平均路長為pij，Tij的根頂點存儲的元素xm，其左子樹Tl和右子樹Tr的平均路長分別為pl和pr。由于Tl和Tr中頂點深度是它們在Tij中的深度減1，所以得到：     由于Ti是關于集合xi , ··· , xm-1的一棵二叉搜索樹，故Pl>=Pi,m-1。若Pl>

13、Pi,m-1，則用Ti,m-1替換Tl可得到平均路長比Tij更小的二叉搜索樹。這與Tij是最優二叉搜索樹矛盾。故Tl是一棵最優二叉搜索樹。同理可證Tr也是一棵最優二叉搜索樹。因此最優二叉搜索樹問題具有最優子結構性質。     3、遞推關系：     根據最優二叉搜索樹問題的最優子結構性質可建立計算pij的遞歸式如下：     初始時：     記 wi,j pi,j為m(i,j) ,則m(1,n)=w1,n p1,n=p1,n為所求的最優值。計算

14、m(i,j)的遞歸式為：         4、求解過程：    1)沒有內部節點時，構造T10,T21,T32，Tn+1n    2)構造只有1個內部結點的最優二叉搜索樹T11,T22, Tnn，可以求得mii 同時可以用一個數組存做根結點元素為：s11=1, s22=2snn=n    3)構造具有2個、3個、n個內部結點的最優二叉搜索樹。        r （ 起止下標的差）    0

15、60; T11, T22       , ，     Tnn，    1   T12, T23, ，Tn-1n，    2   T13, T24, ，Tn-2n，        r   T1r+1, T2r+2, ，Tii+r，Tn-rn        n-1   T1n     具體代碼如下：     cpp vie

16、w plain copy1. /3d11-1 最優二叉搜索樹 動態規劃  2. #include "stdafx.h"  3. #include <iostream>   4. using namespace std;  5.   6. const int N = 3;  7.   8. void 

17、;OptimalBinarySearchTree(double a,double b,int n,double *m,int *s,double *w);  9. void Traceback(int n,int i,int j,int *s,int f,char ch);  10.   11. int main()  12.   13.  

18、60;  double a = 0.15,0.1,0.05,0.05;  14.     double b = 0.00,0.5,0.1,0.05;  15.   16.     cout<<"有序集的概率分布為："<<endl;  17.     for(int 

19、i=0; i<N+1; i+)  18.       19.         cout<<"a"<<i<<"="<<ai<<",b"<<i<<"="<<bi<<endl;  20.   

20、    21.   22.     double *m = new double *N+2;  23.     int *s = new int *N+2;  24.     double *w =new double *N+2; 

21、; 25.   26.     for(int i=0;i<N+2;i+)    27.         28.         mi = new doubleN+2;    29.      

22、   si = new intN+2;    30.         wi = new doubleN+2;    31.        32.   33.     OptimalBinarySearchTree(a,b

23、,N,m,s,w);  34.     cout<<"二叉搜索樹最小平均路長為："<<m1N<<endl;  35.     cout<<"構造的最優二叉樹為:"<<endl;  36.     Traceback(N,1,N,s,0,'0');  37.   3

24、8.     for(int i=0;i<N+2;i+)    39.         40.         delete mi;  41.         delete si;  42.  

25、       delete wi;  43.        44.     delete m;  45.     delete s;  46.     delete w;  47.    &

26、#160;return 0;  48.   49.   50. void OptimalBinarySearchTree(double a,double b,int n,double *m,int *s,double *w)  51.   52.     /初始化構造無內部節點的情況  53.     for(int&

27、#160;i=0; i<=n; i+)  54.       55.         wi+1i = ai;  56.         mi+1i = 0;  57.       58.

28、60; 59.     for(int r=0; r<n; r+)/r代表起止下標的差  60.       61.         for(int i=1; i<=n-r; i+)/i為起始元素下標  62.        &

29、#160;  63.             int j = i+r;/j為終止元素下標  64.   65.             /構造Tij 填寫wij,mij,sij  66.     &#

30、160;       /首選i作為根，其左子樹為空，右子樹為節點  67.             wij=wij-1+aj+bj;  68.             mij=mi+1j;  69.   

31、60;         sij=i;  70.   71.             /不選i作為根，設k為其根，則k=i+1，j  72.             /左子樹為節點：i,i+1k-1,右子樹為節點

32、：k+1,k+2,j  73.             for(int k=i+1; k<=j; k+)  74.               75.          &#

33、160;      double t = mik-1+mk+1j;  76.   77.                 if(t<mij)  78.            

34、       79.                     mij=t;  80.                   

35、0; sij=k;/根節點元素  81.                   82.               83.           

36、0; mij+=wij;  84.           85.       86.   87.   88. void Traceback(int n,int i,int j,int *s,int f,char ch)  89.   90.  

37、0;  int k=sij;  91.     if(k>0)  92.       93.         if(f=0)  94.           95.      

38、       /根  96.             cout<<"Root："<<k<<" (i:j):("<<i<<","<<j<<")"<<endl;  97.  &#

39、160;        98.         else  99.           100.             /子樹  101.    &

40、#160;        cout<<ch<<" of "<<f<<":"<<k<<" (i:j):("<<i<<","<<j<<")"<<endl;  102.       &

41、#160;   103.   104.         int t = k-1;  105.         if(t>=i && t<=n)  106.          

42、0;107.             /回溯左子樹  108.             Traceback(n,i,t,s,k,'L');  109.           110.   

43、;      t=k+1;  111.         if(t<=j)  112.           113.             /回溯右子樹  114. 

44、0;           Traceback(n,t,j,s,k,'R');  115.           116.       117.           4、構造最優解：   算法OptimalB

45、inarySearchTree中用sij保存最優子樹T(i,j)的根節點中的元素。當sin=k時，xk為所求二叉搜索樹根節點元素。其左子樹為T(1,k-1)。因此，i=s1k-1表示T(1,k-1)的根節點元素為xi。依次類推，容易由s記錄的信息在O(n)時間內構造出所求的最優二叉搜索樹。     5、復雜度分析與優化：   算法中用到3個數組m,s和w，故所需空間復雜度為O(n2)。算法的主要計算量在于計算。對于固定的r，它需要的計算時間O(j-i+1)=O(r+1)。因此算法所耗費的總時間為：。事實上，由動態規劃加速原理之四邊形不

46、等式可以得到：而此狀態轉移方程的時間復雜度為O(n2)。由此，對算法改進后的代碼如下：cpp view plain copy1. /3d11-1 最優二叉搜索樹 動態規劃加速原理 四邊形不等式  2. #include "stdafx.h"  3. #include <iostream>   4. using namespace std;  5.   6. cons

47、t int N = 3;  7.   8. void OptimalBinarySearchTree(double a,double b,int n,double *m,int *s,double *w);  9. void Traceback(int n,int i,int j,int *s,int f,char ch);  10. &

48、#160; 11. int main()  12.   13.     double a = 0.15,0.1,0.05,0.05;  14.     double b = 0.00,0.5,0.1,0.05;  15.   16.     cout<<"有序集的概率分布為：&

49、quot;<<endl;  17.     for(int i=0; i<N+1; i+)  18.       19.         cout<<"a"<<i<<"="<<ai<<",b"<<i&

50、lt;<"="<<bi<<endl;  20.       21.   22.     double *m = new double *N+2;  23.     int *s = new int *N+2;  24.  

51、;   double *w =new double *N+2;  25.   26.     for(int i=0;i<N+2;i+)    27.         28.         mi = new

52、60;doubleN+2;    29.         si = new intN+2;    30.         wi = new doubleN+2;    31.        

53、32.   33.     OptimalBinarySearchTree(a,b,N,m,s,w);  34.     cout<<"二叉搜索樹最小平均路長為："<<m1N<<endl;  35.     cout<<"構造的最優二叉樹為:"<<endl;  36.   

54、60; Traceback(N,1,N,s,0,'0');  37.   38.     for(int i=0;i<N+2;i+)    39.         40.         delete mi;  41.   &#

55、160;     delete si;  42.         delete wi;  43.        44.     delete m;  45.     delete s;  46. &#

56、160;   delete w;  47.     return 0;  48.   49.   50. void OptimalBinarySearchTree(double a,double b,int n,double *m,int *s,double *w)  51.   52.   

57、60; /初始化構造無內部節點的情況  53.     for(int i=0; i<=n; i+)  54.       55.         wi+1i = ai;  56.         mi+1i

58、60;= 0;  57.         si+1i = 0;  58.       59.   60.     for(int r=0; r<n; r+)/r代表起止下標的差  61.       62.

59、60;       for(int i=1; i<=n-r; i+)/i為起始元素下標  63.           64.             int j = i+r;/j為終止元素下標  65.

60、            int i1 = sij-1>i?sij-1:i;  66.             int j1 = si+1j>i?si+1j:j;  67.   68.    

61、0;        /構造Tij 填寫wij,mij,sij  69.             /首選i作為根，其左子樹為空，右子樹為節點  70.             wij=wij-1+aj+bj;  

62、71.             mij=mii1-1+mi1+1j;  72.             sij=i1;  73.   74.             /不選i作為根

63、，設k為其根，則k=i+1，j  75.             /左子樹為節點：i,i+1k-1,右子樹為節點：k+1,k+2,j  76.             for(int k=i1+1; k<=j1; k+)  77.   

64、0;           78.                 double t = mik-1+mk+1j;  79.   80.           &#

65、160;     if(t<mij)  81.                   82.                     mij=t;

66、  83.                     sij=k;/根節點元素  84.                   85.     

67、          86.             mij+=wij;  87.           88.       89.   90.   91. voi

68、d Traceback(int n,int i,int j,int *s,int f,char ch)  92.   93.     int k=sij;  94.     if(k>0)  95.       96.       &

69、#160; if(f=0)  97.           98.             /根  99.             cout<<"Root："<<k&l

70、t;<" (i:j):("<<i<<","<<j<<")"<<endl;  100.           101.         else  102.        

71、60;  103.             /子樹  104.             cout<<ch<<" of "<<f<<":"<<k<<" (i:j):(&q

72、uot;<<i<<","<<j<<")"<<endl;  105.           106.   107.         int t = k-1;  108.      &#

73、160;  if(t>=i && t<=n)  109.           110.             /回溯左子樹  111.            &

74、#160;Traceback(n,i,t,s,k,'L');  112.           113.         t=k+1;  114.         if(t<=j)  115.      

75、60;    116.             /回溯右子樹  117.             Traceback(n,t,j,s,k,'R');  118.         

76、60; 119.       120.   運行結果如圖： 【算法學習】最優二叉查找樹（動態規劃）標簽： 算法c2012-10-19 11:07 20641人閱讀 評論(5) 收藏 舉報本文章已收錄于：  算法與數據結構知識庫 分類：數據結構與算法（18） 版權聲明：本文為博主原創文章，未經博主允許不得轉載。一、什么是最優二叉查找樹最優二叉查找樹：給定n個互異的關鍵字組成的序列K=<k1,k2,.,k

77、n>，且關鍵字有序（k1<k2<.<kn），我們想從這些關鍵字中構造一棵二叉查找樹。對每個關鍵字ki，一次搜索搜索到的概率為pi。可能有一些搜索的值不在K內，因此還有n+1個“虛擬鍵”d0,d1,.,dn，他們代表不在K內的值。具體：d0代表所有小于k1的值，dn代表所有大于kn的值。而對于i = 1,2,.,n-1,虛擬鍵di代表所有位于ki和ki+1之間的值。對于每個虛擬鍵，一次搜索對應于di的概率為qi。要使得查找一個節點的期望代價（代價可以定義為：比如從根節點到目標節點的路徑上節點數目）最小，就需要建立一棵最優二叉查找樹。圖一顯示了給定上面的概率分布pi、qi，

78、生成的兩個二叉查找樹的例子。圖二就是在這種情況下一棵最優二叉查找樹。概率分布：i012345pi0.150.100.050.100.20qi0.050.100.050.050.050.10已知每個關鍵字以及虛擬鍵被搜索到的概率，可以計算出一個給定二叉查找樹內一次搜索的期望代價。假設一次搜索的實際代價為檢查的節點的個數，即所發現的節點的深度加1.計算一次搜索的期望代價等式為：建立一棵二叉查找樹，如果是的上式最小，那么這棵二叉查找樹就是最優二叉查找樹。而且有下式成立：二、最優二叉查找樹的最優子結構最優子結構：如果一棵最優二叉查找樹T有一棵包含關鍵字ki,.,kj的子樹T'，那么這可子樹T&

79、#39;對于關鍵字Ki,.,kj和虛擬鍵di-1,.dj的子問題也必定是最優的。可以應用剪貼法證明。根據最優子結構，尋找最優解：給定關鍵字ki,.,kj，假設kr(i<=r<=j)是包含這些鍵的一棵最優子樹的根。其左子樹包含關鍵字ki,.,kr-1和虛擬鍵di-1,.,dr-1，右子樹包含關鍵字kr+1,.,kj和虛擬鍵dr,.dj。我們檢查所有的候選根kr,就保證可以找到一棵最優二叉查找樹。遞歸解：定義ei,j為包含關鍵字ki,.,kj的最優二叉查找樹的期望代價，最終要計算的是e1,n。當j = i - 1時，此時子樹中只有虛擬鍵，期望搜索代價為ei,i - 1 = qi-1.當

80、j >= i時，需要從ki,.,kj中選擇一個根kr，然后分別構造其左子樹和右子樹。下面需要計算以kr為根的樹的期望搜索代價。然后選擇導致最小期望搜索代價的kr做根。現在需要考慮的是，當一棵樹成為一個節點的子樹時，期望搜索代價怎么變化？子樹中每個節點深度都增加1.期望搜索代價增加量為子樹中所有概率的總和。對一棵關鍵字ki,.,kj的子樹，定義其概率總和為：因此，以kr為根的子樹的期望搜索代價為：而因此ei,j可以進一步寫為：這樣推導出最終的遞歸公式為：三、代碼實現（C+）：cpp view plain copy print?1. /最優二叉查找樹 

81、 2.   3. #include <iostream>  4.   5. using namespace std;  6.   7. const int MaxVal = 9999;  8.   9. const int n = 5;  10. /搜索到根節點和虛擬鍵的概率  11.

82、double pn + 1 = -1,0.15,0.1,0.05,0.1,0.2;  12. double qn + 1 = 0.05,0.1,0.05,0.05,0.05,0.1;  13.   14. int rootn + 1n + 1;/記錄根節點  15. double wn + 2n + 2;/子樹概率總和

83、  16. double en + 2n + 2;/子樹期望代價  17.   18. void optimalBST(double *p,double *q,int n)  19.   20.     /初始化只包括虛擬鍵的子樹  21.     for (int i =

84、60;1;i <= n + 1;+i)  22.       23.         wii - 1 = qi - 1;  24.         eii - 1 = qi -

85、0;1;  25.       26.   27.     /由下到上，由左到右逐步計算  28.     for (int len = 1;len <= n;+len)  29.       30.     &#

86、160;   for (int i = 1;i <= n - len + 1;+i)  31.           32.             int j = i + l

87、en - 1;  33.             eij = MaxVal;  34.             wij = wij - 1 + pj + qj;  35. 

88、0;           /求取最小代價的子樹的根  36.             for (int k = i;k <= j;+k)  37.          

89、0;    38.                 double temp = eik - 1 + ek + 1j + wij;  39.            

90、;     if (temp < eij)  40.                   41.                   

91、  eij = temp;  42.                     rootij = k;  43.                

92、0;  44.               45.           46.       47.   48.   49. /輸出最優二叉查找樹所有子樹的根  50. void printRoot() 

93、; 51.   52.     cout << "各子樹的根：" << endl;  53.     for (int i = 1;i <= n;+i)  54.       55.     

94、0;   for (int j = 1;j <= n;+j)  56.           57.             cout << rootij << " "&#

95、160; 58.           59.         cout << endl;  60.       61.     cout << endl;  62.   63. 

96、0; 64. /打印最優二叉查找樹的結構  65. /打印出i,j子樹，它是根r的左子樹和右子樹  66. void printOptimalBST(int i,int j,int r)  67.   68.     int rootChild = rootij;/子樹根節點  69.     if (rootChild

97、0;= root1n)  70.       71.         /輸出整棵樹的根  72.         cout << "k" << rootChild << "是根" &l

98、t;< endl;  73.         printOptimalBST(i,rootChild - 1,rootChild);  74.         printOptimalBST(rootChild + 1,j,rootChild);  75.         retu