当前位置:文档之家› 算法分析与设计实验报告 (2)

算法分析与设计实验报告 (2)

算法分析与设计上机实验报告课程名称:算法分析与设计班级:实验日期:姓名:学号:指导教师:许晓华实验名称:最优二叉搜索树实验地点:主楼1114实验成绩:一、实验目的及要求1.进一步掌握最优二叉树的含义。

2.掌握最优二叉树的结构特征。

3.认真阅读和掌握动态规划法秋最有搜索二叉树实验的程序。

4.上机运行本程序。

5.保存和打印出程序的运行结果,并结合程序进行分析。

6.按照你二叉树的操作需要,可重新改写主程序并运行,请上交文件清单和运行结果二、实验环境及设备微机一台:Intel 酷睿2双核操作系统:Microsoft Windows XP Professional工具软件:Microsoft Visual C++ 6.0三、实验内容及实验步骤动态规划——最优二叉查找树1,问题描述:给定一个有序序列K={k1<k2<k3<,……,<kn}和他们被查询的概率P={p1,p2,p3,……,pn},要求构造一棵二叉查找树T,使得查询所有元素的总的代价最小。

对于一个搜索树,当搜索的元素在树内时,表示搜索成功。

当不在树内时,表示搜索失败,用一个“虚叶子节点”来标示搜索失败的情况,因此需要n+1个虚叶子节点{d0<d1<……<dn}。

其中d0表示搜索元素小于k1的失败结果,dn表示搜索元素大于kn的失败情况。

di(0<i<n)表示搜索节点在ki和k(i+1)之间时的失败情况。

对于应di的概率序列是Q={q0,q1,……,qn}。

2,问题分析:在二叉树中T内搜索一次的期望代价为:E[T]=(depth(ki)+1)*pi //对每个i=1~n,搜索成功情况+(depth(di)+1)*qi //对每个i=0~n,搜索失败情况3,问题求解:动态规划步骤一:寻找最优子结构。

一个最优二叉树的子树必定包含连续范围的关键字ki~kj,1<=i<=j<=n,同时也必须含有连续的虚叶子节点di-1~dj。

如果一棵最优二叉查找树T有一棵含有关键字ki~kj的子树T',那么,T'也是一棵最优查找树,这通过剪贴思想可以证明。

现在开始构造最优子结构:在ki~kj中,选定一个r,i<=r<=j,使以kr为根,ki~k(r-1)和k(r+1)~kj为左右孩子的最优二叉树。

注意r=i或者r=j的情况,表示左子树或右子树只有虚叶子节点。

步骤二:一个递归解。

定义e[i,j]为一棵包含关键字ki~kj的最优二叉树的期望代价。

当j=i-1时没有真实的关键在,只有虚叶子节点d(i-1)。

于是:当j=i-1时,e[i,i-1]=q(i-1)。

当j>=i时,需要选择合适的kr作为根节点,然后其余节点ki~K(r-1)和k(r+1)~kj构造左右孩子。

这时要考虑左右孩子这些节点成为一个节点的子树后,它的搜索代价的变化:根据E[T]的计算,得知它们的期望代价增加了“子树中所有概率的总和”w。

w[i,j]=pl // 对每个l=i~j+ql //对每个l=i-1~j于是当j>=i时,e[i,j]=pr + (e[i,r-1]+w[i,r-1])+(e[r+1,j]+w[r+1,j]) = e[i,r-1] + e[r+1,j]+w[i,j];步骤三:计算最优二叉树的期望代价e[i,j]=q(i-1) //如果j=i-1min(e[i,r-1] + e[r+1,j]+w[i,j]),如果i<=j,其中i<=r<=jw[i,j] =q(i-1) 如果j=i-1w[i,j]=w[i,j-1]+pj+qj 如果i<=j实现代码如下:view plaincopy to clipboardprint?1 #include <iostream>2 using namespace std;34 #define MAXNUM 1005 #define MAX 655366 //p中为有序关键字k1到k5的搜索概率,k1<k2<k3<k4<k57 double p[MAXNUM] = {0.00,0.15,0.10,0.05,0.10,0.20};8 double q[MAXNUM] = {0.05,0.10,0.05,0.05,0.05,0.10};9 void optimal_bst(double e[][MAXNUM],int root[][MAXNUM],double w[][MAXNUM],int n)10 {11 int i =0,j=0;12 //针对左或右孩子为空树情况初始化13 for(i = 1;i<=n+1;i++)14 {15 e[i][i-1] = q[i-1];16 w[i][i-1] = q[i-1];17 }18 int l = 0;19 //计算顺序如下:根据计算式:e[i,j] = e[i,r-1]+e[r+1,j首先计算节点个数为1的最优二叉树的代价e[1,1],e[2,2]……接着计算节点个数为1的最优二叉树的代价e[1,2],e[2,3]…………最后计算结点个数为n的最优二叉树的代价e[1,n],利用之前保存的较少结点最优二叉树的结果。

20 for(l = 1;l<=n;l++)21 {22 for(i = 1;i<=n-l+1;i++)23 {24 j = i+l-1;25 e[i][j] = MAX;26 w[i][j] = w[i][j-1] + p[j]+q[j];27 for(int r = i;r<=j;r++)28 {29 do uble t = 0;30 t = e[i][r-1]+e[r+1][j] + w[i][j];31 if (t<e[i][j])32 {33e[i][j]= t;34root[i][j] = t;35 }36 }3738 }39 }4041 }42 int main()43 {44 double e[MAXNUM][MAXNUM];45 int root[MAXNUM][MAXNUM];46 double w[MAXNUM][MAXNUM];4748 optimal_bst(e,root,w,5);4950 for(int i =1;i<=6;i++)51 {52 for(int j = 0;j<=5;j++)53 {54 cout << e[i][j] << " ";55 }56 cout << endl;57 } 这是一个经典的动态规划问题(但厉害的是其中带有一个很神奇的定理),问题是这样的:已知二叉搜索树中每个节点的访问概率,问这棵树整体的搜索时间最短是多少(此时称为最优二叉搜索树)。

众所周知,在二叉搜树中,一次搜索的时间等于待访问节点的深度。

所以整体的搜索时间为:节点i的访问概率 * 节点i的深度所以如果要整体搜索时间最短,则访问概率高的节点应该比较靠近根节点。

乍一听,好像是哈夫曼编码。

但是不同的是,这是二叉搜索树,所有节点的左右顺序(这里指中序遍历的顺序)不能变化。

所以无法像哈夫曼编码那样一味地把概率高的节点往上移(那是一个贪心算法)。

那该怎么办呢?其实我们只要想到这样一个递推关系:一棵树如果是最优二叉搜索树,那么要么它是空树,要么它的左、右子树也是最优二叉搜索树。

这样就得到了动态规划的解法:For size = 1到nFor 所有包含size个元素的子树For 该子树的所有节点i找出其中一个i,使当它为根节点时,左、右子树的最短搜索时间之和最小。

那么该子树的访问时间就是:左、右子树的最短搜索时间之和 + 所有节点的访问概率之和(因为所有节点都下降了一层)。

可见,这个算法的时间复杂度是O(n^3)。

但是有一个神奇的定理,可以把算法的时间效复杂度降到O(n^2),如下:设一个子树的节点为i ~ j(当然,这里说的i ~ j都是从小到大排好序的),则当它是最优二叉搜索树时的根节点root(i, j)满足:root(i, j - 1) <= root(i, j) <= root(i + 1, j)。

这样一来,上面那个算法的第3个For就可以不用循环子树中的所有节点了,只要循环另两个子树的根节点之间的范围就可以了。

而这个范围根据实践表明是很小的。

所以整体的时间复杂度就相当于两层For循环而已。

===========================================//最优二叉搜索树的动态规划算法代码如下:#include <stdio.h>#include <stdlib.h>#include <assert.h>#include <string.h>typedef struct matrix{int row;int col;} matrix;typedef struct minCost{int cost;int mid;} minCost;minCost** func(matrix* mt, ssize_t count){int i, j, step, min, temp, mid;minCost **rows;rows = (minCost **)malloc(count*(sizeof(minCost*)));for(i=0;i<count;i++)rows[i] = (minCost *)malloc((count-i)*sizeof(minCost));for(i=0;i<count;i++){rows[i][0].cost=0;rows[i][0].mid=-1;}for(step=1;step<count;step++)for(j=0;j<count-step;j++){min=mt[j].row*mt[j].col*mt[j+step].col+rows[j][0].cost+rows[j+1][step-1].cost;mid=j;for(i=1;i<step;i++){temp=rows[j][i].cost+rows[j+i+1][step-i-1].cost+mt[j].row*mt[j+i].col*mt[j+step].col;if(min>temp){min=temp;mid=j+i;}}rows[j][step].cost=min;rows[j][step].mid=mid;}printf("%d, %d\n", rows[0][count-1].cost, rows[0][count-1].mid); return rows;}void rel(minCost **mc, ssize_t count){int i;for(i=0;i<count;i++)free(mc[i]);free(mc);}int main(int argc, char *argv[]){minCost **temp;matrix ma[]={{30,35},{35,15},{15,5},{5,10},{10,20},{20,25}};temp=func(ma, sizeof(ma)/sizeof(ma[0]));rel(temp, sizeof(ma)/sizeof(ma[0]));return 0;}四、调试过程及实验结果上程序调试运行的结果为:15125 , 2虽然使用动态规划法可以构造出最优二叉搜索树,但on3的时间复杂性仍然显得太高。

相关主题