57-算法设计

4.10.2　算法设计

采用自底向上的方法求最优解，分为不同规模的子问题，对于每一个小的决策都求最优

（1）确定合适的数据结构

采用一维数组p[]、q[]分别记录实结点和虚结点的搜索概率，c[i][j]表示最优二叉搜索树T(i，j)的搜索成本，w[i][j]表示最优二叉搜索树T(i，j)中的所有实结点和虚结点的搜索概率之和，s[i][j]表示最优二叉搜索树T(i，j)的根节点序号。

（2）初始化

输入实结点的个数n，然后依次输入实结点的搜索概率存储在p[i]中，依次输入虚结点的搜索概率存储在q[i]中。令c[i][i−1]=0.0，w[i][i−1]=q[i−1]，其中i= 1，2，3，…，n+1。

（3）循环阶段

• 按照递归式计算元素规模是1的{s_i}（j=i）的最优二叉搜索树搜索成本c[i][j]，并记录最优策略，即树根s[i][j]，i= 1，2，3，…，n。
• 按照递归式计算元素规模是2的{s_i，s_i+1}（j=i+1）的最优二叉搜索树搜索成本c[i][j]，并记录最优策略，即树根s[i][j]，i= 1，2，3，…，n−1。
• 以此类推，直到求出所有元素{s₁，…，s_n} 的最优二叉搜索树搜索成本c[1][n]和最优策略s[1][n]。

（4）构造最优解

• 首先读取s[1][n]，令k=s[1][n]，输出s_k为最优二叉搜索树的根。
• 判断如果k−1<1，表示虚结点e_k−1是s_k的左子树；否则，递归求解左子树Construct_ Optimal_BST(1,k−1,1)。
• 判断如果kn，输出虚结点e_k是s_k的右孩子；否则，输出s[k+1][n]是s_k的右孩子，递归求解右子树Construct_Optimal_BST(k+1，n，1)。