Go语言视频零基础入门到精通

javalearner

1、最优二叉搜索树的动态规则算法

二叉搜索树是一颗满足如下条件的树：
1.每个节点包含一个键值
2.每个节点有最多两个孩子
3.对于任意两个节点x和y，它们满足下述搜索性质:
a)如果y在x 的左子树里，则key[y] <=key[x]
b)如果y在x的右子树里，则key[y]>=key[x]

基于统计知识，我们可统计出一个数表（集合）中各元素的查找概率，理解为集合各元素的出现频率。比如中文输入法字库中各词条（单字、词组等）的先验概率，针对用户习惯可以自动调整词频――所谓动态调频、高频先现原则，以减少用户翻查次数。这就是最优二叉查找树问题：查找过程中键值比较次数最少，或者说希望用最少的键值比较次数找到每个关键码（键值）。为解决这样的问题，显然需要对集合的每个元素赋予一个特殊属性――查找概率。这样我们就需要构造一颗最优二叉查找树。
   
  
   
   

     
   

     
   
  

2、问题给出
n个键{a1,a2,a3......an},a1 < a2 <・ ・ ・ < an，其相应的查找概率为{p1,p2,p3......pn}。构成最优BST, ，求这棵树的平均查找次数C[1, n]（耗费最低)。换言之，如何构造这棵最优BST，使得C[1, n] 最小。
C[i, j] 表示由{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[1, 2]→C[1, 3] →... →C[1, n]。为不失一般性用
C[i, j] 表示由{ai,ai+1,......aj}构成的BST的耗费。其中1≤i ≤j ≤n。这棵树表示为Tij。从中选择一个键ak作根节点，它的左子树为Tik-1，右子树为Tk+1j。要求选择的k 使得整棵树的平均查找次数C[i, j]最小。左右子树递归执行此过程。（根的生成过程）

4、递推计算式


5、基本算法如下


6、具体实现代码

1. import java.util.Scanner;
   
2. import java.util.Arrays;
   
3. public class BST{
   
4.    static int max=Integer.MAX_VALUE;
   
5.    public static  void main(String args[]){
   
6.       int num;
   
7.       Scanner in=new Scanner(System.in);
   
8.      
   
9.      //所有数据均从键盘获取，第一行一个数据表示节点个数；从第二行各个数据开始表示各个节点的概率
   
10.      /*
    
11.       5
    
12.       0.15 0.10 0.05 0.10 0.20
    
13.      */
    
14.       /*
    
15.        6
    
16.        0.3 0.15 0.05 0.3 0.15 0.05
    
17.       */
    
18.        num=in.nextInt();
    
19.        double p[]=new double[num+1];
    
20.        for(int i=1;i< num+1;i++)
    
21.          p[i]=in.nextDouble();
    
22.       //创建主表；
    
23.        double c[][]=new double[num+2][num+1];
    
24.          for(int i=0;i< c[i].length;i++)
    
25.            Arrays.fill(c[i],0);
    
26.       //创建根节点表；
    
27.        int r[][]=new int[num+2][num+1];
    
28.             for(int i=0;i< r[i].length;i++)
    
29.            Arrays.fill(r[i],0);
    
30.      //动态规划实现最优二叉查找树的期望代价求解。。
    
31.       OptimalBST(num,p,c,r);
    
32.       System.out.printf("该最优二叉查找树的期望代价为：%f
33. ",c[1][num]);
    
34.      
    
35.    
    
36.       //给出最优二叉查找树的中序遍历结果；
    
37.       System.out.printf("构造成的最优二叉查找树的前序遍历结果为：");
    
38.      OptimalBSTPrint(1,num,r);
    
39. 
    
40.    }
    
41.   
    
42.    public static void OptimalBST(int num,double[] p,double[][]c,int[][] r) {
    
43.      int j=0;
    
44.      int kmin=0;
    
45.      double temp=0.0;
    
46.      double sum=0.0;
    
47.      for(int i=1;i< num+1;i++)//主表和根表元素的初始化
    
48.      {
    
49.      
    
50.          c[i][i-1]=0;
    
51.          c[i][i]=p[i];
    
52.          r[i][i]=i;
    
53.      }
    
54.      c[num+1][num]=0;
    
55.      for(int d=1;d<=num-1;d++)//加入节点序列
    
56.      {
    
57.          for(int i=1;i<=num-d;i++)
    
58.          {
    
59.              j=i+d;
    
60.              temp=max;
    
61.              for(int k=i;k<=j;k++)//找最优根
    
62.              {
    
63.                  if(c[i][k-1]+c[k+1][j]< temp)
    
64.                  {
    
65.                      temp=c[i][k-1]+c[k+1][j];
    
66.                      kmin=k;
    
67.                  }
    
68.              }
    
69.              r[i][j]=kmin;//记录最优根
    
70.              sum=p[i];
    
71.              for(int s=i+1;s<=j;s++)
    
72.                  sum+=p[s];
    
73.              c[i][j]=temp+sum;
    
74.          }
    
75.      }
    
76. }
    
77. //采用递归方式实现最优根的输出，最优根都是保存在r[i][j]中的。。。
    
78. public static  void OptimalBSTPrint(int first,int last,int[][] r)
    
79. {
    
80. 
    
81.      int k;
    
82.      if(first<=last)
    
83.      {
    
84.          k=r[first][last];
    
85.          System.out.printf("%d  ",k);
    
86.          OptimalBSTPrint(first,k-1,r);
    
87.          OptimalBSTPrint(k+1,last,r);
    
88.      }
    
89. }
    
90. }

复制代码

运行结果：
5
0.15 0.10 0.05 0.10 0.20
该最优二叉查找树的期望代价为：1.300000
构造成的最优二叉查找树的前序遍历结果为：4  1  2  3  5




  
  
   
   

     
   

     
   
  

复制代码

源码下载：http://file.javaxxz.com/2014/12/6/000713656.zip