动态规划方法生成最优二叉查找树
1、概念引入
基于统计先验知识，我们可统计出一个数表（集合）中各元素的查找概率，理解为集合各元素的出现频率。比如中文输入法字库中各词条（单字、词组等）的先验概率，针对用户习惯可以自动调整词频——所谓动态调频、高频先现原则，以减少用户翻查次数。这就是最优二叉查找树问题：查找过程中键值比较次数最少，或者说希望用最少的键值比较次数找到每个关键码（键值）。为解决这样的问题，显然需要对集合的每个元素赋予一个特殊属性——查找概率。这样我们就需要构造一颗最优二叉查找树。
2、问题给出
n个键{a1,a2,a3......an},其相应的查找概率为{p1,p2,p3......pn}。构成最优BST,表示为T 1 n ，求这棵树的平均查找次数C[1, n]（耗费最低)。换言之，如何构造这棵最优BST，使得
C[1, n] 最小。
3、分段方法
动态规划法策略是将问题分成多个阶段，逐段推进计算，后继实例解由其直接前趋实例解计算得到。对于最优BST问题，利用减一技术和最优性原则，如果前n-1个节点构成最优BST，加入一个节点 a n 后要求构成规模n的最优BST。按 n-1, n-2 , ... , 2, 1 递归，问题可解。自底向上计算：C[1, 2]→C[1, 3] →... →C[1, n]。为不失一般性用
C[i, j] 表示由{a1,a2,a3......an}构成的BST的耗费。其中1≤i ≤j ≤n。这棵树表示为Tij。从中选择一个键ak作根节点，它的左子树为Tik-1，右子树为Tk+1j。要求选择的k 使得整棵树的平均查找次数C[i, j]最小。左右子树递归执行此过程。（根的生成过程）
4、递推计算式
5、基本算法如下
6、具体实现代码（其中所有数据都存放在2.txt中，其内容为：
其中5表示有5个节点，其他数据表示各个节点出现的概率；
1 #include<stdio.h>
2 #include<stdlib.h>
3 #define max 9999
4 void OptimalBST( int , float *, float **, int ** );
5 void OptimalBSTPrint( int , int , int ** );
6 void main()
7 {
8 int i,num;
9 FILE * point;
10 // 所有数据均从2.txt中获取，2.txt中第一个数据表示节点个数；从第二个数据开始表示各个节点的概率
11 point=fopen( " 2.txt " , " r " );
12 if (point== NULL)
13 {
14 printf( " cannot open 2.txt.\n " );
15 exit(- 1 );
16 }
17 fscanf(point, " %d " ,& num);
18 printf( " %d\n " ,num);
19 float *p=( float *)malloc( sizeof ( float )*(num+ 1 ));
20 for (i= 1 ;i<num+ 1 ;i++ )
21 fscanf(point, " %f " ,& p[i]);
22 // 创建主表；
23 float **c=( float **)malloc( sizeof ( float *)*(num+ 2 ));
24 for (i= 0 ;i<num+ 2 ;i++ )
25 c[i]=( float *)malloc( sizeof ( float )*(num+ 1 ));
26 // 创建根表；
27 int **r=( int **)malloc( sizeof ( int *)*(num+ 2 ));
28 for (i= 0 ;i<num+ 2 ;i++ )
29 r[i]=( int *)malloc( sizeof ( int )*(num+ 1 ));
30 // 动态规划实现最优二叉查找树的期望代价求解。。
31 OptimalBST(num,p,c,r);
32 printf( " 该最优二叉查找树的期望代价为：%f \n " ,c[ 1 ][num]);
33 // 给出最优二叉查找树的中序遍历结果；
34 printf( " 构造成的最优二叉查找树的中序遍历结果为： " );
35 OptimalBSTPrint( 1 , 4 ,r);
36
37 }
38 void OptimalBST( int num, float *p, float **c, int ** r)
39 {
40 int d,i,j,k,s,kmin;
41 float temp,sum;
42 for (i= 1 ;i<num+ 1 ;i++) // 主表和根表元素的初始化
43 {
44
45 c[i][i- 1 ]= 0 ;
46 c[i][i]= p[i];
47 r[i][i]= i;
48 }
49 c[num+ 1 ][num]= 0 ;
50 for (d= 1 ;d<=num- 1 ;d++) // 加入节点序列
51 {
52 for (i= 1 ;i<=num-d;i++ )
53 {
54 j=i+ d;
55 temp= max;
56 for (k=i;k<=j;k++) // 找最优根
57 {
58 if (c[i][k- 1 ]+c[k+ 1 ][j]< temp)
59 {
60 temp=c[i][k- 1 ]+c[k+ 1 ][j];
61 kmin= k;
62 }
63 }
64 r[i][j]=kmin; // 记录最优根
65 sum= p[i];
66 for (s=i+ 1 ;s<=j;s++ )
67 sum+= p[s];
68 c[i][j]=temp+ sum;
69 }
70 }
71 }
72 // 采用递归方式实现最优根的输出，最优根都是保存在r[i][j]中的。。。
73 void OptimalBSTPrint( int first, int last, int ** r)
74 {
75
76 int k;
77 if (first<= last)
78 {
79 k= r[first][last];
80 printf( " %d " ,k);
81 OptimalBSTPrint(first,k- 1 ,r);
82 OptimalBSTPrint(k+ 1 ,last,r);
83 }
84 }
7、最终运行结果：
8、参考文献：
（1）算法导论
（2）数据结构 严蔚敏
（3）网上下载的一个ppt（算法设计与分析，第八章）
标签: c语言 算法
作者： Leo_wl
出处： http://www.cnblogs.com/Leo_wl/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
版权信息