假如我们要设计一个简单的程序将一段英文翻译成法语,那么就需要为每个
英语单词找到对应的法语单词,简单的做法是在单词库中对每个单词进行遍
历查找。更快一点的做法是,我们可以将单词库建成一颗平衡二叉搜索树
——用英文单词做Key,对应的法语单词做附属信息。第二种方法,虽然可以保
证每个单词的查询时间控制在O(lgn),不过却也有不合理之处。由于单词出现
的频率有高有低,于是一些常用单词离根节点很远,而一些很生僻的单词却
在根节点附近。可见用一颗平衡二叉搜索树来做这个问题并不是非常高效,在
这儿就引出了另一种二叉查找树——最优二叉查找树。

问题定义

假设给定一组有序的序列\( K =\),在查找的
过程中被查找的键是\(k_i\)的概率是\(p_i\)。同时因为有一些单词是K
中不存在的,因此我们用n+1个虚拟键来表示这些不存在于K中的键,分别为
\(d_0, d_1, d_2, \dots, d_n\)。其中\(d_0\)代表所有比\(k_1\)
小的键,\(d_n\)表示 所有比\(k_n\)大的键,对于\(i = 1, 2, \dots, n-1 \),
虚拟键\(d_i\)表示所有位于\( ki 和 k{i+1} \)之间的键。对于每一
个\(d_i\),我们有一个概率\(q_i\)。

对于每次搜索,非成功,即失败,所以有:

因为对于每个关键字和虚拟键的概率都是已知的,所以我们可以求出一颗二叉搜
索树的期望值:

\(dpth_T\)代表结点在树种的深度。而我们的目标就是要建立起一颗搜索期望值最
小的二叉树——也就是最优二叉搜索树。

动态规划的解法

很显然,假如\(k_i\)是最优二叉搜索树的根节点,那么它的左子树和右子树必然是最
优二叉搜索树。由此可见,这个问题拥有最优子结构。

要注意到,当一棵树成为另一棵树的子树的时候,由于每个结点的深度增加了1,所
以搜索期望代价增加量为所有结点的概率总和:

所以对于一棵根结点为\(k_r\)包含有结点\(k_i, \dots, k_j\)的最优二叉搜索树,
我们有:

\[ e[i, j] = p_r + e(r[i, r-1] + w(i, r-1)) + (e[r+1, j] + w(r+1, j)).\]

注意到:\(w(i, j) = w(i, r-1) + p_r + w(r + 1, j)\),所以:

\[ e[i, j] = e[i, r - 1] + e[r + 1, j] + w(i, j) \].

如此一来,我们可以建立起递归式了:

\( e[i, j] \)记录了最优二叉查找树中的期望搜索代价,为了可以建立起二叉搜索
树的结构,我们需要一个\( root[i, j] \)来记录根结点\( k_r \)的下标。

在下面的伪码中,用表\( e[i \dots n, 0 \dots n] \)来存储\( e[i, j] \)。
第一维需要到\( n + 1 \)而不是\( n \)因为有子树只包含虚拟键\( d_n \),
我们需要计算和存储\( e[n+1, n] \).第二维需要从0开始是因为有子树只包含虚拟
键\(d_0\),我们需要计算和存储\( e[1, 0] \). 此外,除了用表\( root[i, j] \)
来记录根结点\(k_r\)的下标外,我们还需要一个表\( w[1 \dots n+1, 0 \dots n] \),
来记录\( w(i, j) \)以提高效率——这样就不必每次都从头计算\( w(i, j) \)了。
对于\( 1 \leq i \leq n \). 且\(j \geq i\), 我们有:

\[ w(i, j) = w(i, j - 1) + p_j + q_j \]

伪码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
OPTIMAL-BST(p, q, n)
let e[1 .. n + 1, 0 .. n], w[1, n + 1, 0 .. n],
and root[1..n, 1..n] be new tables
for i = 1 to n + 1
e[i, i - 1] = q<sub>i-1</sub>
w[i, i - 1] = q<sub>i-1</sub>
for l = 1 to n
for i = 1 to n - l + 1
j = i + l - 1
e[i, j] = ∞
w[i, j] = w[i, j -1] + p<sub>j</sub> + q<sup>j</sup>
for r = i to j
t = e[i, r - 1] + e[r + 1, j] + w[i, j]
if t < e[i, j]
e[i, j] = t
root[i, j] = r
return e and root

C++的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<iostream>
#include<numeric>
#include"LSC.h"

double optimal_bst(float *p , float* q, int n , int **root)
{
double **e=dob_array<double>(n+2,n+1);
double **w=dob_array<double>(n+2, n+1);
for (int i=1; i != n+2; ++i)
{
e[i][i-1]=q[i-1];
w[i][i-1]=q[i-1];
}
for(int l=1; l!=n+1 ; ++l){
for(int i=1; i !=n+2-l; ++i){
int j=i+l-1;
e[i][j]=std::numeric_limits<double>::max();
w[i][j]=w[i][j-1]+p[j-1]+q[j];
for(int r=i; r != j+1; ++r){
double t=e[i][r-1]+w[i][j]+e[r+1][j];
if(t<e[i][j]){
e[i][j]=t;
root[i-1][j-1]=r;
}
}
}
}
double result= e[1][5];
delete_dob_array<double>(e,n+2);
delete_dob_array<double>(w,n+2);
return result;
}

int main()
{
float q[6]={0.05, 0.10, 0.05, 0.05, 0.05, 0.10};
float p[5]={0.15, 0.10, 0.05, 0.10, 0.20 };
const int size=5;
int **root =dob_array<int> (size, size);
std::cout<<optimal_bst(p,q, size,root)<<std::endl;
std::cin.get();
delete_dob_array(root,size);
}

上面用到的两个函数dob_arraydelete_dob_array是在前一篇笔记
最长公共子序列中实现的。

此外,我们可以定义一个函数来输出一下树的结构,也就是课后练习15.5-2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void print_optimal_bst(int **root, int i , int j)
{
if(i>j)
return;
else{
int r=root[i-1][j-1];
std::cout<<"k"<<r<<std::endl;
std::cout<<"k"<<r<<"'s lefe child is ";
if(r-1<i)
std::cout<<"d"<<r-1<<std::endl;
else
print_optimal_bst(root, i, r-1);
std::cout<<"k"<<r<<"'s right child is ";
if(r+1>j)
std::cout<<"d"<<r<<std::endl;
else
print_optimal_bst(root, r+1, j);
}
}