首页 > 专题系列 > 算法分析 > 最优二分查找树-动态规划
2014
07-05

最优二分查找树-动态规划

最优二分查找树

给一个已排序的数组 keys[0.. n-1] 作为待搜索的关键字和 一个 freq[0.. n-1]数组表示搜索每个关键字的频率。构建一个最优二分查找树,使得搜索的总花费最小。首先,需要定义二分查找的花费,每个节点的花费为该节点的高度乘以该节点查找的频率。根节点的高度为1.

Given a sorted array keys[0.. n-1] of search keys and an array freq[0.. n-1] of frequency counts, wherefreq[i] is the number of searches to keys[i]. Construct a binary search tree of all keys such that the total cost of all the searches is as small as possible.

 例 1
输入:  keys[] = {10, 12}, freq[] = {34, 50}
有以下两种可能:
        10                       12
          \                     / 
           12                 10
          I                     II
tree I 的花费为 34*1 + 50*2 = 134
tree II 的花费为 50*1 + 34*2 = 118 

例2
输入:  keys[] = {10, 12, 20}, freq[] = {34, 8, 50}
有以下几种可能:
    10                12                 20         10              20
      \             /    \              /             \            /
      12          10     20           12               20         10  
        \                            /                 /           \
         20                        10                12             12  
     I               II             III             IV             V
其中第5棵树的花费最小: 1*50 + 2*34 + 3*8 = 142

可以发现,总花费的大小其实和keys[]数组无关的。主要是元素的查找频率有关。
最优子结构

由于数组是已排序的,并且根据二分查找树的性质,给定关键字keys[i,...,j],假设keys[r](i<=r<=j)是包含这些键的一棵最优子树的根,则其左子树包含关键字keys[i,...,r-1] 右子树包含关键字keys[r+1,...,j]。我们检查所有的候选根keys[r],就保证可以找到一棵最优二叉查找树。可以得出如下的递归方程:

quicklatex.com-88a5d8f68aec043b6aa0c5c8bc49feab_l3

重叠子问题

下面是根据上面的递归方程写出的递归程序代码:

public class OptimalSearchTree {
	public static int sum(int freq[], int i, int j) {
		int s = 0;
		for (int k = i; k <= j; k++)
			s += freq[k];
		return s;
	}

	public static int optCost(int freq[], int i, int j) {
		if (i > j)
			return 0;
		if (i == j) {
			return freq[i];
		}
		//计算fsum的原因是:左右子树的高度比当前节点高度大1,因此要对所有节点重复加一次
		int fsum = sum(freq, i, j);
		int min = Integer.MAX_VALUE;
		// 逐个考虑每个顶点为根的情况
		for (int r = i; r <= j; ++r) {
			int cost = optCost(freq, i, r - 1) + optCost(freq, r + 1, j);
			if (cost < min)
				min = cost;
		}
		return min + fsum;
	}

	public static void main(String[] args) {
	    int freq[] = {34, 8, 50};
		System.out.println("Cost of Optimal BST is "+ optCost(freq, 0 , freq.length-1));
	}
}

上面的复杂度为指数级的,有很多子为题被重复计算,可以看出,和矩阵连乘问题很相似。我们可以使用动态规划的方法进行优化,DP算法如下:

	public static int optCostDP(int freq[]) {
		int n = freq.length;
		int dp[][] = new int[n][n];
		for (int i = 0; i < n; i++)
			dp[i][i] = freq[i];

		// l表示树的节点个数
		for (int l = 2; l <= n; l++) {
			for (int i = 0; i <= n - l; i++) {
				// 从i到j,长度为l
				int j = i + l - 1;
				dp[i][j] = Integer.MAX_VALUE;
				for (int r = i; r <= j; r++) {
					int c = ((r > i) ? dp[i][r - 1] : 0)
							+ ((r < j) ? dp[r + 1][j] : 0) + sum(freq, i, j);
					if (c < dp[i][j])
						dp[i][j] = c;
				}
			}
		}
		return dp[0][n-1];
	}

注意
1) 上面算法的时间复杂度为 O(n^4). 可以很容易的优化到 O(n^3) ,主要是对于sum函数,可以预处理所有的和。

2)上面的算法只求出了最小花费,并没有给出树的机构,稍作修改即可构建树。在最内层的循环记录下r(根节点)即可。


  1. int half(int *array,int len,int key)
    {
    int l=0,r=len;
    while(l<r)
    {
    int m=(l+r)>>1;
    if(key>array )l=m+1;
    else if(key<array )r=m;
    else return m;
    }
    return -1;
    }
    这种就能避免一些Bug
    l,m,r
    左边是l,m;右边就是m+1,r;