最优二分检索树 最优二分检索树问题:求一棵使得预期成本最小的二分检索树 一、问题引出   或是一棵空树;或者是具有如下性质的非空二叉树:  (1)左子树的所有结点均小于根的值;  (2)右子树的所有结点均大于根的值; 对于一个给定的标识符集合,可能有若干棵不同的二分检索树: 不同形态的二分检索树对标识符的检索性能是不同的。 设给定的标识符集合是{a1,a2,…,an},并假定a1<a2< … < an。设,P(i)是对ai检索的概率,Q(i)是正被检索的标识符X恰好满足: ai<X<a…

2013年5月14日 0条评论 3点热度 阅读全文

问题的描述: n个作业{1,2,…,n}要在由2台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工,然后在M2上加工。M1和M2加工作业i所需的时间分别为ai和bi。 流水作业调度问题要求确定这n个作业的最优加工顺序,使得从第一个作业在机器M1上开始加工,到最后一个作业在机器M2上加工完成所需的时间最少。 调度规则 (1 ) 把全部ai和bi分类成非降序列,ai和bi分别是第i个作业在两个机器上所需要的时间。 (2 ) 按照这一分类次序考察此序列: 如果序列中下一个数是aj 且作业j还没调…

2013年5月14日 0条评论 2点热度 阅读全文

1、可靠性设计 可靠性设计:一个系统由n级设备串联而成,为了增强可靠性,每级都可能并联了不止一台同样的设备。所以每级用的设备越多系统的可靠性越高。但是设备都是有成本的,假定设备Di的成本是ci,设计该系统允许的投资不超过c,那么,该如何设计该系统(即各级采用多少设备)使得这个系统的可靠性最高。试设计一个动态规划算法求解可靠性设计。 如果第i级的设备Di的台数为mi,那么这mi台设备同时出现故障的概率为(1-ri)mi ,从而第i级的可靠性就变成1-(1-ri)mi 。例如,假定ri=0.99 ,mi=2,于是这一级…

2013年5月14日 0条评论 4点热度 阅读全文

贪心算法 一、贪心算法定义 贪婪算法是一种改进了的分级处理方法。其核心是根据题意选取一种量度标准。然后将这多个输入排成这种量度标准所要求的顺序,按这种顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行解,则不把此输入加到这部分解中。这种能够得到某种量度意义下最优解的分级处理方法称为贪婪算法。 贪心算法总是作出在当前看来是最好的选择。也就是说贪心算法不从整体最优上加以考虑,它所作出的选择只是在某种意义上的局部最优选择。虽然贪心算法不是对所有问题都能得到整体最优解(0/1背…

2013年5月11日 0条评论 3点热度 阅读全文

贪心算法 一、贪心算法定义 贪婪算法是一种改进了的分级处理方法。其核心是根据题意选取一种量度标准。然后将这多个输入排成这种量度标准所要求的顺序,按这种顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行解,则不把此输入加到这部分解中。这种能够得到某种量度意义下最优解的分级处理方法称为贪婪算法。 贪心算法总是作出在当前看来是最好的选择。也就是说贪心算法不从整体最优上加以考虑,它所作出的选择只是在某种意义上的局部最优选择。虽然贪心算法不是对所有问题都能得到整体最优解(0/1背…

2013年5月11日 0条评论 2点热度 阅读全文

B-tree的引入 可以讲B理解成 broad 在现代计算机中通常采用分级存储系统,以最简单的二级分级存储策略为例,就是由内存储器与外存储器(磁盘)组成二级存储系统。这一策略的思想是:将最常用的数据副本存放于内存中,而大量的数据存放于外存中,借助有效的算法可以将外存的大存储量与内存高速度的优点结合起来。 一般的,在分级存储系统中,各级存储器的速度有着巨大的差异,仍然以磁盘和内存为例,前者的平均访问速度为10ms左右,而内存储器的平均访问时间为ns级,通常在10~100ns左右,二者之间差异大约为106。因此,为了节…

2012年12月28日 0条评论 3点热度 阅读全文

平衡二叉树(AVL) 一、 平衡二叉树 在二叉查找树T中,若所有结点的平衡因子的绝对值均不超过1,则称T为一棵AVL树。 平衡二叉树又称AVL树,它是具有如下性质的二叉树: • 左、右子树是平衡二叉树; • 所有结点的左、右子树深度之差的绝对值≤ 1 为了方便起见,给每个结点附加一个数字,给出该结点左子树与右子树的高度差。这个数字称为结点的平衡因子balance。这样,可以得到AVL树的其它性质: • 任一结点的平衡因子只能取:-1、0或 1;如果树中任意一个结点的平衡因子的绝对值大于1,则这棵…

2012年12月28日 0条评论 0点热度 阅读全文

二叉查找树(Binary Search Tree) 一、二叉查找树的定义 ----或是一棵空树;或者是具有如下性质的非空二叉树:  (1)左子树的所有结点均小于根的值;  (2)右子树的所有结点均大于根的值; 结论:中序遍历一棵二叉查找树可以得到一个按关键字递增的有序序列。 1、查找 查找的递归实现 : private Node binTSearchRe(BinTreeNode rt, Object ele) { if (rt == null) return null; switch (stra…

2012年12月28日 0条评论 31点热度 阅读全文