学步园

问题：假设n个已经排序的关键字{1,2,…,n}，他们被搜索的概率分别为{p1,p2,…,pn}，其它搜索值则被这些关键字分割，它们的概率为{q0,q1,…,qn}。q0代表搜索值小于1的可能性，qn代表搜索值大于n的可能性，qi（i=1,2,,…,n-1）代表搜索之大于i小于i+1的可能性。构建二叉搜索树，使得值搜索的期望代价最小。

分析：令a[i][j]代表i->j的最优二叉搜索树的期望代价。于是我们可以得到以下递推式：

这个算法的复杂度为O(n^3)。
Knuth已经证明对于所有的1 <= i < j <= n，总存在最优子树的根使得root[i][j-1] <= root[i][j] <= root[i+1][j]。所以只要在i<j时，在求min操作中，使root[i][j-1] <= k <= root[i+1][j]。此时算法复杂度为O(n^2)。

代码：

#include <iostream><br /> #define MAXLENGTH 100<br /> #define MAX 100<br /> #define LEFT false<br /> #define RIGHT true<br /> using namespace std;<br /> /**<br /> * @brief Create the optimal binary search tree. The time complexity is O(n^3).<br /> *<br /> * @param p[]: the possibility of inner nodes. The nodes are assumed to have been sorted by their key<br /> * @param q[]: the possibility of outer nodes. These nodes have the keys who are not in the binary search tree<br /> * @param n: the number of inner nodes<br /> * @param a[][MAXLENGTH]: a[i][j] means the minimum cost of tree i->j<br /> * @param root[][MAXLENGTH]: root[i][j] means the root of tree i->j<br /> */<br /> void OptimalBinarySearchTree(double p[], double q[], int n, double a[][MAXLENGTH], int root[][MAXLENGTH])<br /> {<br /> double w[MAXLENGTH][MAXLENGTH];<br /> //initial states<br /> for (int i = 0; i <= n; ++i)<br /> {<br /> a[i + 1][i] = q[i];<br /> w[i + 1][i] = q[i];<br /> }<br /> for (int len = 1; len <= n; ++len)<br /> {<br /> for (int i = 1; i <= n - len + 1; ++i)<br /> {<br /> int j = i + len - 1;<br /> a[i][j] = MAX;<br /> w[i][j] = w[i][j - 1] + p[j] + q[j];<br /> //if use {for (int k = root[i][j-1]; k <= root[i+1][j]; ++k)}, the time complexity will be O(n^2)<br /> //this method only applies to such a situation when 1 <= i < j <= n, so when len == 1, we should not use this method<br /> for (int k = i; k <= j; ++k)<br /> {<br /> double temp = a[i][k - 1] + a[k + 1][j] + w[i][j];<br /> //get the minimum cost<br /> if (temp < a[i][j])<br /> {<br /> a[i][j] = temp;<br /> root[i][j] = k;<br /> }<br /> }<br /> }<br /> }<br /> }<br /> /**<br /> * @brief Print the tree<br /> *<br /> * @param root[][MAXLENGTH]: the root matrix<br /> * @param start: the start position of the tree<br /> * @param end: the end position of the tree<br /> * @param k: the parent, -1 means root has no parent<br /> * @param LeftOrRight: the left or right subtree of the parent<br /> */<br /> void PrintTree(int root[][MAXLENGTH], int start, int end, int k, bool LeftOrRight)<br /> {<br /> if (k == -1)<br /> {<br /> cout << "the root is p" << root[start][end] << endl;<br /> PrintTree(root, start, root[start][end] - 1, root[start][end], LEFT);<br /> PrintTree(root, root[start][end] + 1, end, root[start][end], RIGHT);<br /> }<br /> else if (LeftOrRight == LEFT)<br /> {<br /> if (start <= end)<br /> {<br /> cout << "the left child of p" << k << " is p" << root[start][end] << endl;<br /> PrintTree(root, start, root[start][end] - 1, root[start][end], LEFT);<br /> PrintTree(root, root[start][end] + 1, end, root[start][end], RIGHT);<br /> }<br /> else<br /> {<br /> cout << "the left child of p" << k << " is q" << start - 1 << endl;<br /> }<br /> }<br /> else<br /> {<br /> if (start <= end)<br /> {<br /> cout << "the right child of p" << k << " is p" << root[start][end] << endl;<br /> PrintTree(root, start, root[start][end] - 1, root[start][end], LEFT);<br /> PrintTree(root, root[start][end] + 1, end, root[start][end], RIGHT);<br /> }<br /> else<br /> {<br /> cout << "the right child of p" << k << " is q" << start - 1 << endl;<br /> }<br /> }<br /> }<br /> int main()<br /> {<br /> double p[MAXLENGTH];<br /> double q[MAXLENGTH];<br /> double a[MAXLENGTH][MAXLENGTH];<br /> int root[MAXLENGTH][MAXLENGTH];<br /> int n;<br /> while (cin >> n, n != 0)<br /> {<br /> for (int i = 1; i <= n; ++i)<br /> {<br /> cin >> p[i];<br /> }<br /> for (int i = 0; i <= n; ++i)<br /> {<br /> cin >> q[i];<br /> }<br /> OptimalBinarySearchTree(p, q, n, a, root);<br /> cout << a[1][n] << endl;<br /> PrintTree(root, 1, n, -1, true);<br /> }<br /> }