动态规划最优二叉搜索树.doc

《动态规划最优二叉搜索树.doc》由会员分享，可在线阅读，更多相关《动态规划最优二叉搜索树.doc（10页珍藏版）》请在三一文库上搜索。

1、常M仏卑沱课程设计说明书（论文）用纸摘要动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可 能会有许多可行解，每个解都对应一个值，要求找到具有最优值的解。其基本 思想是将待求解问题分解成若干个子问题，先求解子问题，并把所有已解子问 题的答案记录到一个表中，而不考虑这些子问题的答案以后是否被用到。用动 态规划算法来求解最优二叉搜索树问题，可以描述为对于有序集S及S的存取概率分布（a0，bl，a1，,bn，an），在所有表示有序集S的二叉搜索树中找出 一棵开销最小的二叉搜索树。动态规划算法的有效性依赖于问题本身具有最优子结构性质和子问题重叠 性质。最典型的就是路由器中的路由搜索引擎查

2、找一条指定的路由最坏情况下 最多只用查找31次。该文给出了用动态规划算法构造最优二叉搜索树的详细步骤，并用C+语言具体实现了该算法，用一定的空间换取时间，提高了解决本问题的效率。关键词：动态规划，最优二叉搜索树，最优子结构I常M仏卑沱课程设计说明书（论文）用纸1问题描述1.2问题分析2.3算法设计3.4算法实现4.5测试分析6.结论7.参考文献8.2常M仏卑沱课程设计说明书（论文）用纸1问题描述给定一个有序序列K=k1vk2<k3<, , ,<k n和他们被查询的概率P=p1,p2,p3, ,pn,要求构造一棵二叉查找树 T,使得查询所有元素的总的代价最小。对于一个搜索树，当

3、搜索的元素在树内时，表示搜索成功。当不 在树内时，表示搜索失败，用一个“虚叶子节点”来标示搜索失败的情况，因 此需要n+1个虚叶子节点d0<d1<, <dn。其中dO表示搜索元素小于k1的失 败结果，dn表示搜索元素大于kn的失败情况。di（ 0<i<n ）表示搜索节点在ki 和k（i+1）之间时的失败情况。对于应di的概率序列是Q=qO,q1, , ,qn。在 最有二叉搜索树问题是指已给出一株二叉树的中序遍历（或需要你全排列枚 举），以及每个节点搜索概率，搜索到一层花费1,问如何安排这颗二叉树使搜索花费的期望值最小。第1页共8页常M仏卑沱课程设计说明书(论文)用

4、纸2问题分析最优二叉搜索树问题具有最优子结构性质。证明：设Tij是有序集xi,xj 关于存取概率分布(ai-1, bi,，bj, aj)的一棵最优二叉搜索树，平均路长为 pij。Tij的根结点存储元素xk。其左右子树Tl和Tr的平均路长分别为pl和pr。 由于Tl是关于集合xi ,，xk-1的一个二叉搜索树，故pl > pi,k1。如果pl > pi,k-1,那么用Ti,k-1替换Tl可得到平均路长比Tij更小的二叉搜索树。这与Tij 是最优二叉搜索树相矛盾。所以，左子树Tl是一棵最优二叉搜索树，同理可证右子树Tr也是一棵最优二叉搜索树，即最优二叉搜索树的子树也是最优二叉搜 索树。

5、建立递归关系式若最优二叉搜索树Ti,j的根结点为k,最小平均路长为pi,j,mi,j 表示 Ti,j 的开销，则有 mi,j=wi,jpi,j ，其中 <E:2008 学术交 流200学术交流第四卷第八期(2008总第35期 第1次96篇1.3软件设计开 发tr01.tif，可建立下列递归关系：Mi,j=bk+(mi,k-1+wi,k-1)+ (mk+1,j+wk+1,j)而 wi,j=bk+wi,k-1+wk+1,j则 mi,j=wi,j+mi,k-1+mk+1,j(1)将k=i+1，i+2，,j分别代入<1>式，选取使mi,j达到最小的K，这样递 归关系式改为：mi,j=

6、wi,j+minmi,k-1+mk+1,jmi,i-1=0， K i <n解递归关系，m1,n就是所求的最优值。将对应于mi,j的断开位置k记 录在si,j中(也称为根表，记录子树的根)，以便构造最优解。根据记录的 最优断开位置si,j,可以容易地构造出最优解。3算法设计寻找最优子结构。一个最优二叉树的子树必定包含连续范围的关键字kikj，l<=i<=j<=n，同时也必须含有连续的虚叶子节点 di-1dj。如果一棵最优 二叉查找树T有一棵含有关键字kikj的子树T'，那么，T'也是一棵最优查找树， 这通过剪贴思想可以证明。现在开始构造最优子结构：在kik

7、j中，选定一个r,i<=r<=j，使以kr为根， kik(r-1)和k(r+1)kj为左右孩子的最优二叉树。注意r=i或者r=j的情况，表示 左子树或右子树只有虚叶子节点。定义ei,j为一棵包含关键字kikj的最优二叉树的期望代价。当j=i-1时没 有真实的关键在，只有虚叶子节点d(i-1)。于是：当 j=i-1 时，ei,i-1=q(i-1)。当j>=i时，需要选择合适的kr作为根节点，然后其余节点kiK(r-1)和k(叶1)kj构造左右孩子。这时要考虑左右孩子这些节点成为一个节点的子树后， 它的搜索代价的变化：根据ET的计算，得知它们的期望代价增加了子树中所有概率的总和”

8、 wwi,j= pl / 对每个 l=ij+ql /对每个 l=i-1j于是当 j>=i 时，ei,j=pr + (ei,r-1+wi,r-1)+(er+1,j+wr+1,j)= ei,r-1 +er+ 1,j+wi,j;第3页共8页常M仏卑沱课程设计说明书（论文）用纸4算法实现计算最优二叉树的期望代价ei,j= q(i-1)如果 j=i-1min(ei,r-1 + er+1,j+wi,j),如果 i<=j，其中 i<=r<=jwi,j=q(i-1)如果 j=i-1wi,j=wi,j-1+pj+qj 如果 i<=j3代码实现view pla in copy to

9、clipboardpri nt?#i nclude <iostream>using n amespace std;#define MAXNUM 100#define MAX 65536/p中为有序关键字k1到k5的搜索概率，k1vk2vk3<k4vk5double pMAXNUM = 0.00,0.15,0.10,0.05,0.10,0.20;double qMAXNUM = 0.05,0.10,0.05,0.05,0.05,0.10;void optimal_bst(double eMAXNUM,i nt rootMAXNUM,double wMAXNUM,i nt n)i

10、nt i =0,j=0;/针对左或右孩子为空树情况初始化for(i = 1;i<=n+1;i+)eii-1 = qi-1;wii-1 = qi-1;int l = 0;/计算顺序如下：根据计算式：ei,j = ei,r-1+er+1,j首先计算节点个数为1的最优二叉树的代价e1,1,e2,2 接着计算节点个数为1的最优二叉树的 代价e1,2,e2,3最后计算结点个数为n的最优二叉树的代价e1,n,利用之前保存的较少结点最优二叉树的结果。for(l = 1;l<=n;l+)for(i = 1;i<=n-l+1;i+)j = i+l-1;eij = MAX;wij = wij-1

11、 + pj+qj；for(int r = i;r<=j;r+)double t = 0;t = eir-1+er+1j + wij; if(t<eij)eij= t;rootij = r;int mai n()double eMAXNUMMAXNUM; in t rootMAXNUMMAXNUM; double wMAXNUMMAXNUM; optimal_bst(e,root,w,5);for(i nt i =1;i<=6;i+)for(i nt j = 0;jv=5;j+)cout << eij << ""cout <&l

12、t; en dl; 5测试分析在二叉树中T内搜索一次的期望代价为：(depth(ki)+1)*pi 对每个i=1n,搜索成功情况+(depth(di)+1)*qi /对每个i=On，搜索失败情况i,j=q(i-1) 如果 j=i-1min(ei,r-1 + er+1,j+wi,j),如果 i<=j，其中 i<=r<=jwi,j=q(i-1)如果 j=i-1wi,j=wi,j-1+pj+qj 如果 i<=j第6页共8页常M仏卑沱课程设计说明书（论文）用纸最优二叉搜索树是整个搜索成本最低的二叉搜索树。具体来说就是：给定键值序列K = <k1, k2, . . . ,

13、kn>，k1 < k2 < < kn,其中键值ki,被搜索的概率 为pi，要求以这些键值构建一颗二叉搜索树 T,使得搜索的期望成本最低（搜 索成本为检查的节点数）。对于键值ki,如果其在构造的二叉搜索树里的深度（离开树根的分支数）为depthT（ki），则搜索该键值的成本=depthT（ki） +1 （需要加上深度为0的树根节点）。由于每个键值被搜索的概率分别为 pi=1,2,3,n本算法分析与设计课程设计是综合分析和理解动态规划算法，综合运用C、C+或JAVA等程序设计语言，设计的过程也是一个不断摸索的过程。只有对所作题 目有了清楚的认识和理解，有了思想上的充分准备，

14、才能在设计过程中“胸有 成竹”。所以我们对题目进行了比较详尽的考虑。当实际操作过程中遇到这样那样的困难，就通过查看资料、上网等方式解决。通过这次课程设计，我们对动态规划算法有了更深的认识，同时也更加熟练了 C、C+ffi JAVA程序设计语言的运用，是开发人员必不可少的有力工具。 同时，我们学到了如何用算法的思想分析一个给定的问题，最终动手解决问题。在整个过程中，需要不断的调试，更改代码，当中，我们遇到了很多棘手问题。 在不断思考、调试后，不仅锻炼了我的实际动手能力，更锻炼了我们发现问题、 分析问题的能力。第7页共8页常M仏卑沱课程设计说明书（论文）用纸参考文献1 孙雄勇Visual C+ 6.0 实用教程.北京：中国铁道出版社，20042 谭浩强编著.C+面向对象程序设计.北京：清华大学出版社，20063 王晓东编著.计算机算法设计与分析.北京：电子工业出版社，2007.54 常友渠.动态规划的探讨与研究M.重庆电力高等专科学报,2008.9.龚雄兴,堆与动态规划M,湖北襄樊学院，2003.6张洁,朱莉娟.贪心算法与动态规划的比较M.新乡师范高等专科科学学报2005.9.第8页共8页