最優二叉搜索樹的動態規劃算法研究

摘要：動態規劃算法的有效性依賴于問題本身具有最優子結構性質和子問題重疊性質。該文給出了用動態規劃算法構造最優二叉搜索樹的詳細步驟，并用C++語言具體實現了該算法。用一定的空間換取時間，提高了解決本問題的效率。

關鍵詞：動態規劃算法；最優子結構；子問題重疊；最優二叉搜索樹

中圖分類號：TP311文獻標識碼：A文章編號：1009-3044(2008)35-2188-02

The Dynamic Programming Algorithm Research of Optimal Binary Search Tree

TAO Rong1，2， ZHAO Wen-jing1

(1.Xi'an University of Architecture and Technology， Xi'an 710055， China; 2.Luoyang Institute of Science and Technology， Luoyang471023， China)

Abstract: The effectiveness of dynamic programming algorithm depends onproblems with the nature of optimal substructure and overlapping subproblems. In this paper， the detailed steps is given on constructing optimal binary search trees with theDynamic Programming Algorithm， And using C++ language Specifically achieves the algorithm. With a certain space for time， the efficiency of resolving this problem is improved.

Key words: dynamic programming algorithm; optimal substructure; overlapping subproblems; optimal binary search tree

1 引言

動態規劃算法通常用于求解具有某種最優性質的問題。在這類問題中，可能會有許多可行解，每個解都對應一個值，要求找到具有最優值的解。其基本思想是將待求解問題分解成若干個子問題，先求解子問題，并把所有已解子問題的答案記錄到一個表中，而不考慮這些子問題的答案以后是否被用到。用動態規劃算法來求解最優二叉搜索樹問題，可以描述為對于有序集S及S的存取概率分布(a0，b1，a1，…， bn，an)，在所有表示有序集S的二叉搜索樹中找出一棵開銷最小的二叉搜索樹。

2 動態規劃算法求解最優二叉搜索樹的步驟

2.1 最優子結構性質分析

最優二叉搜索樹問題具有最優子結構性質。

證明:設Tij是有序集{xi，…，xj}關于存取概率分布(ai-1，bi，…，bj，aj)的一棵最優二叉搜索樹，平均路長為pij。Tij的根結點存儲元素xk。其左右子樹Tl和Tr的平均路長分別為pl和pr。由于Tl是關于集合{xi，…，xk-1}的一個二叉搜索樹，故pl≥pi，k-1。如果pl＞pi，k-1，那么用Ti，k-1替換Tl可得到平均路長比Tij更小的二叉搜索樹。這與Tij是最優二叉搜索樹相矛盾。所以，左子樹Tl是一棵最優二叉搜索樹，同理可證右子樹Tr也是一棵最優二叉搜索樹，即最優二叉搜索樹的子樹也是最優二叉搜索樹。

2.2 建立遞歸關系式

若最優二叉搜索樹Ti，j的根結點為k，最小平均路長為pi，j，m[i，j]表示Ti，j的開銷，則有m[i，j]=wi，jpi，j，其中，可建立下列遞歸關系：

M[i，j]=bk+(m[i，k-1]+wi，k-1)+ (m[k+1，j]+wk+1，j)

而 wi，j=bk+wi，k-1+wk+1，j

則m[i，j]=wi，j+m[i，k-1]+m[k+1，j]（1）

將k=i+1，i+2，…，j分別代入<1>式，選取使m[i，j]達到最小的K，這樣遞歸關系式改為：

m[i，j]=wi，j+min{m[i，k-1]+m[k+1，j]}m[i，i-1]=0，1≤i≤n

2.3 遞歸計算最優值

解遞歸關系，m[1，n]就是所求的最優值。將對應于m[i，j]的斷開位置k記錄在s[i，j]中（也稱為根表，記錄子樹的根），以便構造最優解。

2.4 構造最優解

根據記錄的最優斷開位置s[i，j]，可以容易地構造出最優解。

3 用C++語言實現算法

#include

#define MaxN 50

void OptBST (ofstream out， int n， int a[]， int b[]， int m[][MaxN]，int s[][MaxN])

{ int w[MaxN][MaxN];

for(int i=0; i<=n; i++)

{w[i+1][i]=a[i];m[i+1][i]= 0; s[i+1][i]= 0; }

for(int r=0; r

for(i=1; i<=n-r; i++)

{ int j=i+r;

int i1 = s[i][j-1]>i? s[i][j-1] : i;

int j1 = s[i+1][j]>i? s[i+1][j] : j;

w[i][j] = w[i][j-1]+a[j]+b[j];

m[i][j]= m[i][i1-1]+m[i1+1][j];

s[i][j]= i1;

for(int k=i1+1; k<=j1; k++)

{ int t=m[i][k-1]+ m[k+1][j];

if(t<=m[i][j]) m[i][j]=t， s[i][j]=k;

}

m[i][j] += w[i][j];

}

}

void TraceBack(ofstream out，int n，int i， int j，intm[][MaxN]，int s[][MaxN]，int f， char ch)

{ int k=s[i][j];

if(k>0)

{ if(f==0)

out<<\"Root \"<

else

out<

int t=k-1;

if(t>=i t<=n) TraceBack(out， n， i， t， m， s， k， 'L');

t=k+1;

if(t<=j) TraceBack(out， n， t， j， m， s， k， 'R');

}

}

void main(void)

{ void OptBST( ofstream out， int n， int a[]， int b[]，int m[][MaxN]， int s[][MaxN] );

void TraceBack( ofstream out， int n， int i， int j，intm[][MaxN]， int s[][MaxN]， int， char);

intn，a[MaxN]， b[MaxN]， m[MaxN][MaxN]，s[MaxN][MaxN]， i， j ;

ifstream in(\"OptBSTin.txt\");

cin>>n;

ofstream out(\"OptBSTout.txt\");

cout<<\"n=\"<

for(i=1; i<=n; i++){ cin>>b[i]; cout<<\" \"<

for(i=0; i<=n; i++){ cin>>a[i]; cout<<\" \"<

in.close();

OptBST(out，n，a，b，m，s);

out<<\"\OptimalBinarySearchTree ASL=\" <

out<<\"\ RelationNode ij\----------------------\\";

i=1， j=n; int f=0;

TraceBack(out，n，i，j，m，s，f，'0');

out.close();

4 源程序運行結果

設S={‘D’，‘H’，‘S’}，且S的存取概率分布為{a0，b1，a1，b2，a2，b3，a3}={0.08，0.10，0.18，0.12，0.20，0.23，0.09}，構造一棵最優二叉搜索樹。如圖1、圖2。（為計算方便可將存取概率整數化）

根據圖2所示的結果，構造的最優二叉搜索樹如圖3所示。

5 結束語

動態規劃算法是對貪心算法和分治法的一種折衷，它所解決的問題通常具有最優子結構性質和子問題重疊性質。文中給出了動態規劃算法的設計思想、適用性以及用它求解最優二叉搜索樹的詳細步驟，并用C++語言給出了實現求最優二叉搜索樹問題的動態規劃算法的具體源碼，稍加分析可知，該算法的時間復雜度為O(n2)，空間復雜度為O(n2)，通過犧牲空間來換取時間，提高了解決最優二叉搜索樹問題的效率。

參考文獻：

[1] 王曉東.計算機算法設計與分析[M].北京:電子工業出版社，2005.

[2] Alsuwaiyel M H.算法設計技巧與分析[M].北京:電子工業出版社，2004.

[3] Levitin A.算法設計與分析基礎[M].北京:清華大學出版社，2004.