 上传我的文档
 下载
 收藏
该文档贡献者很忙，什么也没留下。
 下载此文档
正在努力加载中...
最优二叉搜索树-第六章 动态规划算法
下载积分：2000
内容提示：最优二叉搜索树-第六章 动态规划算法
文档格式：PDF|
浏览次数：55|
上传日期： 12:16:37|
文档星级：
该用户还上传了这些文档
最优二叉搜索树-第六章 动态规划算法
官方公共微信您所在位置： &
&nbsp&&nbsp&nbsp&&nbsp
第6章 动态规划法sdwb.ppt67页
本文档一共被下载：
次 ,您可全文免费在线阅读后下载本文档。
文档加载中...广告还剩秒
需要金币：100 &&
你可能关注的文档：
··········
··········
组合问题中的动态规划法
0/1背包问题
最长公共子序列问题 6.3.1
0/1背包问题 在0/1背包问题中，物品i或者被装入背包，或者不被装入背包，设xi表示物品i装入背包的情况，则当xi 0时，表示物品i没有被装入背包，xi 1时，表示物品i被装入背包。根据问题的要求，有如下约束条件和目标函数：
（式6.9） （式6.10） 于是，问题归结为寻找一个满足约束条件式6.9，并使目标函数式6.10达到最大的解向量X
x1, x2, …, xn 。 证明0/1背包问题满足最优性原理。
设 x1, x2, …, xn 是所给0/1背包问题的一个最优解，则
x2, …, xn 是下面一个子问题的最优解： 如若不然，设 y2, …, yn 是上述子问题的一个最优解，则
因此， 这说明 x1, y2, …, yn 是所给0/1背包问题比 x1, x2, …, xn 更优的解，从而导致矛盾。 0/1背包问题可以看作是决策一个序列 x1, x2, …, xn ，对任一变量xi的决策是决定xi 1还是xi 0。在对xi-1决策后，已确定了 x1, …, xi-1 ，在决策xi时，问题处于下列两种状态之一： （1）背包容量不足以装入物品i，则xi 0，背包不增加价值； （2）背包容量可以装入物品i，则xi 1，背包的价值增加了vi。 这两种情况下背包价值的最大者应该是对xi决策后的背包价值。令V i, j 表示在前i 1≤i≤n 个物品中能够装入容量为j（1≤j≤C）的背包中的物品的最大值，则可以得到如下动态规划函数： V i, 0
0 （式6.11） （式6.12） 背包剩余容量不足以放下i物体，不放，价值不变，容量不变 背包剩余容量可以放下i物体，则挑选放与不放两者价值大者 把前面i个物品装入容量为0的背包和把0个物品装入容量为j的背包，得到的价值均为0。 式6.11表明：把前面i个物品装入容量为0的背包和把0个物品装入容量为j的背包，得到的价值
正在加载中，请稍后...1、概念引入
　　基于统计先验知识，我们可统计出一个数表（集合）中各元素的查找概率，理解为集合各元素的出现频率。比如中文输入法字库中各词条（单字、词组等）的先验概率，针对用户习惯可以自动调整词频&&所谓动态调频、高频先现原则，以减少用户翻查次数。这就是最优二叉查找树问题：查找过程中键值比较次数最少，或者说希望用最少的键值比较次数找到每个关键码（键值）。为解决这样的问题，显然需要对集合的每个元素赋予一个特殊属性&&查找概率。这样我们就需要构造一颗最优二叉查找树。
2、问题给出
　　n个键{a1,a2,a3......an},其相应的查找概率为{p1,p2,p3......pn}。构成最优BST,表示为T1n ，求这棵树的平均查找次数C[1, n]（耗费最低)。换言之，如何构造这棵最优BST，使得
C[1, n] 最小。
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] 表示由{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()
//所有数据均从2.txt中获取，2.txt中第一个数据表示节点个数；从第二个数据开始表示各个节点的概率
point=fopen("2.txt","r");
if(point==NULL)
printf("cannot open 2.txt.\n");
fscanf(point,"%d",&num);
printf("%d\n",num);
float *p=(float*)malloc(sizeof(float)*(num+1));
for(i=1;i&num+1;i++)
fscanf(point,"%f",&p[i]);
//创建主表；
float **c=(float**)malloc(sizeof(float*)*(num+2));
for(i=0;i&num+2;i++)
c[i]=(float*)malloc(sizeof(float)*(num+1));
//创建根表；
int **r=(int**)malloc(sizeof(int*)*(num+2));
for(i=0;i&num+2;i++)
r[i]=(int*)malloc(sizeof(int)*(num+1));
//动态规划实现最优二叉查找树的期望代价求解。。
OptimalBST(num,p,c,r);
printf("该最优二叉查找树的期望代价为：%f \n",c[1][num]);
//给出最优二叉查找树的中序遍历结果；
printf("构造成的最优二叉查找树的中序遍历结果为：");
OptimalBSTPrint(1,4,r);
38 void OptimalBST(int num,float*p,float**c,int**r)
int d,i,j,k,s,
float temp,
for(i=1;i&num+1;i++)//主表和根表元素的初始化
c[i][i-1]=0;
c[i][i]=p[i];
r[i][i]=i;
c[num+1][num]=0;
for(d=1;d&=num-1;d++)//加入节点序列
for(i=1;i&=num-d;i++)
for(k=i;k&=j;k++)//找最优根
if(c[i][k-1]+c[k+1][j]&temp)
temp=c[i][k-1]+c[k+1][j];
r[i][j]=//记录最优根
for(s=i+1;s&=j;s++)
sum+=p[s];
c[i][j]=temp+
72 //采用递归方式实现最优根的输出，最优根都是保存在r[i][j]中的。。。
73 void OptimalBSTPrint(int first,int last,int**r)
if(first&=last)
k=r[first][last];
printf("%d
OptimalBSTPrint(first,k-1,r);
OptimalBSTPrint(k+1,last,r);
7、最终运行结果：
8、参考文献：
（1）算法导论
（2）数据结构 严蔚敏
（3）网上下载的一个ppt（算法设计与分析，第八章）
阅读(...) 评论()}