动态规划算法学习十例之五
1、最优二叉搜索树的动态规则算法二叉搜索树是一颗满足如下条件的树：
1.每个节点包含一个键值
2.每个节点有最多两个孩子
3.对于任意两个节点x和y，它们满足下述搜索性质:
a)如果y在x 的左子树里，则key <=key
b)如果y在x的右子树里，则key>=key
基于统计知识，我们可统计出一个数表（集合）中各元素的查找概率，理解为集合各元素的出现频率。比如中文输入法字库中各词条（单字、词组等）的先验概率，针对用户习惯可以自动调整词频——所谓动态调频、高频先现原则，以减少用户翻查次数。这就是最优二叉查找树问题：查找过程中键值比较次数最少，或者说希望用最少的键值比较次数找到每个关键码（键值）。为解决这样的问题，显然需要对集合的每个元素赋予一个特殊属性——查找概率。这样我们就需要构造一颗最优二叉查找树。
2、问题给出
n个键{a1,a2,a3......an},a1 < a2 <· · · < an，其相应的查找概率为{p1,p2,p3......pn}。构成最优BST, ，求这棵树的平均查找次数C（耗费最低)。换言之，如何构造这棵最优BST，使得C 最小。
C 表示由{ai,ai+1,......aj}构成的BST的耗费.
对于键值ai, 如果其在构造的二叉搜索树里的深度（离开树根的分支数）为L(ai)，
则搜索该键值的成本= L(ai) +1（需要加上深度为0的树根节点）。
3、分段方法
动态规划法策略是将问题分成多个阶段，逐段推进计算，后继实例解由其直接前趋实例解计算得到。对于最优BST问题，利用减一技术和最优性原则，如果前n-1个节点构成最优BST，加入一个节点an 后要求构成规模n的最优BST。按 n-1, n-2 , ... , 2, 1 递归，问题可解。自底向上计算：C→C →... →C。为不失一般性用
C 表示由{ai,ai+1,......aj}构成的BST的耗费。其中1≤i ≤j ≤n。这棵树表示为Tij。从中选择一个键ak作根节点，它的左子树为Tik-1，右子树为Tk+1j。要求选择的k 使得整棵树的平均查找次数C最小。左右子树递归执行此过程。（根的生成过程）
4、递推计算式
http://dl.iteye.com/upload/attachment/0074/5854/1bd0ae8e-92db-35d6-8e11-737e1603769b.png
5、基本算法如下
http://dl.iteye.com/upload/attachment/0074/5856/e066be93-b275-3552-975c-44371c6a046f.png
6、具体实现代码
import java.util.Scanner;import java.util.Arrays; public class BST{ static int max=Integer.MAX_VALUE; public staticvoid main(String args[]){ int num; Scanner in=new Scanner(System.in); //所有数据均从键盘获取，第一行一个数据表示节点个数；从第二行各个数据开始表示各个节点的概率 /* 5 0.15 0.10 0.05 0.10 0.20 */ /* 6 0.3 0.15 0.05 0.3 0.15 0.05 */ num=in.nextInt(); double p[]=new double; for(int i=1;i<num+1;i++) p=in.nextDouble(); //创建主表； double c[][]=new double; for(int i=0;i<c.length;i++) Arrays.fill(c,0); //创建根节点表； int r[][]=new int; for(int i=0;i<r.length;i++) Arrays.fill(r,0); //动态规划实现最优二叉查找树的期望代价求解。。 OptimalBST(num,p,c,r); System.out.printf("该最优二叉查找树的期望代价为：%f \n",c); //给出最优二叉查找树的中序遍历结果； System.out.printf("构造成的最优二叉查找树的前序遍历结果为："); OptimalBSTPrint(1,num,r); } public static void OptimalBST(int num,double[] p,double[][]c,int[][] r) { int j=0; int kmin=0; double temp=0.0; double sum=0.0; for(int i=1;i<num+1;i++)//主表和根表元素的初始化 { c=0; c=p; r=i; } c=0; for(int d=1;d<=num-1;d++)//加入节点序列 { for(int i=1;i<=num-d;i++) { j=i+d; temp=max; for(int k=i;k<=j;k++)//找最优根 { if(c+c<temp) { temp=c+c; kmin=k; } } r=kmin;//记录最优根 sum=p; for(int s=i+1;s<=j;s++) sum+=p; c=temp+sum; } } } //采用递归方式实现最优根的输出，最优根都是保存在r中的。。。 public staticvoid OptimalBSTPrint(int first,int last,int[][] r) { int k; if(first<=last) { k=r; System.out.printf("%d",k); OptimalBSTPrint(first,k-1,r); OptimalBSTPrint(k+1,last,r); } }}
运行结果：
5
0.15 0.10 0.05 0.10 0.20
该最优二叉查找树的期望代价为：1.300000
构造成的最优二叉查找树的前序遍历结果为：41235
http://dl.iteye.com/upload/attachment/0074/5858/0b6c0c55-a656-3eaf-bb91-b366cf8f48f2.gif
下载源码：
页:
[1]