- 浏览: 604224 次
- 来自: ...
文章分类
最新评论
-
lgh1992314:
相同的元素呢
一种离散化方法 -
HelloSummerR:
圆心的位置是随机的,于是圆的部分会落到canvas外,那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio:
好久没见到sokuban了,这有个java版的,带源码,可以参 ...
求推箱子的最小步数(java) -
肖泽文:
太好了,谢谢你。。有中文注释!
HTML5 推箱子游戏过关演示动画 -
swm8023:
删除操作,将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
1、最优二叉搜索树的动态规则算法
二叉搜索树是一颗满足如下条件的树:
1.每个节点包含一个键值
2.每个节点有最多两个孩子
3.对于任意两个节点x和y,它们满足下述搜索性质:
a)如果y在x 的左子树里,则key[y] <=key[x]
b)如果y在x的右子树里,则key[y]>=key[x]
基于统计知识,我们可统计出一个数表(集合)中各元素的查找概率,理解为集合各元素的出现频率。比如中文输入法字库中各词条(单字、词组等)的先验概率,针对用户习惯可以自动调整词频——所谓动态调频、高频先现原则,以减少用户翻查次数。这就是最优二叉查找树问题:查找过程中键值比较次数最少,或者说希望用最少的键值比较次数找到每个关键码(键值)。为解决这样的问题,显然需要对集合的每个元素赋予一个特殊属性——查找概率。这样我们就需要构造一颗最优二叉查找树。
2、问题给出
n个键{a1,a2,a3......an},a1 < a2 <· · · < an,其相应的查找概率为{p1,p2,p3......pn}。构成最优BST, ,求这棵树的平均查找次数C[1, n](耗费最低)。换言之,如何构造这棵最优BST,使得C[1, n] 最小。
C[i, j] 表示由{ai,ai+1,......aj}构成的BST的耗费.
对于键值ai, 如果其在构造的二叉搜索树里的深度(离开树根的分支数)为L(ai),
则搜索该键值的成本= L(ai) +1(需要加上深度为0的树根节点)。
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] 表示由{ai,ai+1,......aj}构成的BST的耗费。其中1≤i ≤j ≤n。这棵树表示为Tij。从中选择一个键ak作根节点,它的左子树为Tik-1,右子树为Tk+1j。要求选择的k 使得整棵树的平均查找次数C[i, j]最小。左右子树递归执行此过程。(根的生成过程)
4、递推计算式
5、基本算法如下
6、具体实现代码
运行结果:
5
0.15 0.10 0.05 0.10 0.20
该最优二叉查找树的期望代价为:1.300000
构造成的最优二叉查找树的前序遍历结果为:4 1 2 3 5
下载源码:
二叉搜索树是一颗满足如下条件的树:
1.每个节点包含一个键值
2.每个节点有最多两个孩子
3.对于任意两个节点x和y,它们满足下述搜索性质:
a)如果y在x 的左子树里,则key[y] <=key[x]
b)如果y在x的右子树里,则key[y]>=key[x]
基于统计知识,我们可统计出一个数表(集合)中各元素的查找概率,理解为集合各元素的出现频率。比如中文输入法字库中各词条(单字、词组等)的先验概率,针对用户习惯可以自动调整词频——所谓动态调频、高频先现原则,以减少用户翻查次数。这就是最优二叉查找树问题:查找过程中键值比较次数最少,或者说希望用最少的键值比较次数找到每个关键码(键值)。为解决这样的问题,显然需要对集合的每个元素赋予一个特殊属性——查找概率。这样我们就需要构造一颗最优二叉查找树。
2、问题给出
n个键{a1,a2,a3......an},a1 < a2 <· · · < an,其相应的查找概率为{p1,p2,p3......pn}。构成最优BST, ,求这棵树的平均查找次数C[1, n](耗费最低)。换言之,如何构造这棵最优BST,使得C[1, n] 最小。
C[i, j] 表示由{ai,ai+1,......aj}构成的BST的耗费.
对于键值ai, 如果其在构造的二叉搜索树里的深度(离开树根的分支数)为L(ai),
则搜索该键值的成本= L(ai) +1(需要加上深度为0的树根节点)。
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] 表示由{ai,ai+1,......aj}构成的BST的耗费。其中1≤i ≤j ≤n。这棵树表示为Tij。从中选择一个键ak作根节点,它的左子树为Tik-1,右子树为Tk+1j。要求选择的k 使得整棵树的平均查找次数C[i, j]最小。左右子树递归执行此过程。(根的生成过程)
4、递推计算式
5、基本算法如下
6、具体实现代码
import java.util.Scanner; import java.util.Arrays; public class BST{ static int max=Integer.MAX_VALUE; public static void main(String args[]){ int num; Scanner in=new Scanner(System.in); //所有数据均从键盘获取,第一行一个数据表示节点个数;从第二行各个数据开始表示各个节点的概率 /* 5 0.15 0.10 0.05 0.10 0.20 */ /* 6 0.3 0.15 0.05 0.3 0.15 0.05 */ num=in.nextInt(); double p[]=new double[num+1]; for(int i=1;i<num+1;i++) p[i]=in.nextDouble(); //创建主表; double c[][]=new double[num+2][num+1]; for(int i=0;i<c[i].length;i++) Arrays.fill(c[i],0); //创建根节点表; int r[][]=new int[num+2][num+1]; for(int i=0;i<r[i].length;i++) Arrays.fill(r[i],0); //动态规划实现最优二叉查找树的期望代价求解。。 OptimalBST(num,p,c,r); System.out.printf("该最优二叉查找树的期望代价为:%f \n",c[1][num]); //给出最优二叉查找树的中序遍历结果; System.out.printf("构造成的最优二叉查找树的前序遍历结果为:"); OptimalBSTPrint(1,num,r); } public static void OptimalBST(int num,double[] p,double[][]c,int[][] r) { int j=0; int kmin=0; double temp=0.0; double sum=0.0; for(int 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(int d=1;d<=num-1;d++)//加入节点序列 { for(int i=1;i<=num-d;i++) { j=i+d; temp=max; for(int k=i;k<=j;k++)//找最优根 { if(c[i][k-1]+c[k+1][j]<temp) { temp=c[i][k-1]+c[k+1][j]; kmin=k; } } r[i][j]=kmin;//记录最优根 sum=p[i]; for(int s=i+1;s<=j;s++) sum+=p[s]; c[i][j]=temp+sum; } } } //采用递归方式实现最优根的输出,最优根都是保存在r[i][j]中的。。。 public static void OptimalBSTPrint(int first,int last,int[][] r) { int k; if(first<=last) { k=r[first][last]; System.out.printf("%d ",k); OptimalBSTPrint(first,k-1,r); OptimalBSTPrint(k+1,last,r); } } }
运行结果:
5
0.15 0.10 0.05 0.10 0.20
该最优二叉查找树的期望代价为:1.300000
构造成的最优二叉查找树的前序遍历结果为:4 1 2 3 5
下载源码:
发表评论
-
龙抬头
2014-11-10 15:06 632... -
求推箱子的最小步数(java)
2014-05-06 08:32 3775题目(poj1475):推箱子,要求箱子移动步骤最小。如图:T ... -
田忌赛马: POJ 2287(贪心解法)
2013-01-03 19:24 3062POJ 2287问题描述: 你一定听过田忌赛马的故事吧? ... -
回溯法入门学习之二(九宫格与数独)
2012-11-11 08:53 3337回溯法的基本做法是搜索解空间,一种组织得井井有条的,能避 ... -
回溯法入门学习之一
2012-11-10 15:53 1848一: 回溯法 有时我们要得到问题的解,先从其中某一种情况 ... -
SPFA算法求单源最短路径
2012-11-04 23:00 1943很多时候,给定的图存在负权边,这时类似Dijkstra等算法 ... -
图解Bellman-Ford算法
2012-11-03 19:39 5941Bellman-Ford算法: ... -
并查集入门精讲,实例2个(JAVA)
2012-10-30 14:47 4070一、什么是并查集 ... -
深度优先搜索学习五例之五(JAVA)
2012-10-22 15:48 1247一、深度优先搜索遍历磁盘文件目录 import java.io ... -
深度优先搜索学习五例之四(JAVA)
2012-10-21 17:25 2028先继续“深度优先搜索学习五例之三”http://128k ... -
深度优先搜索学习五例之三(JAVA)
2012-10-20 20:43 2316一、深度优先搜索框架一递归实现,流程如下: ... -
深度优先搜索学习五例之二(JAVA)
2012-10-20 12:24 2269继续“深度优先搜索学习五例之一 ”中的第一例子:http:// ... -
深度优先搜索学习五例之一(JAVA)
2012-10-19 14:54 4983深度优先搜索DFS(Depth First Search) ( ... -
广度优先搜索学习五例之五
2012-10-17 21:11 1444如果已经知道搜索的开始状态和结束状态,要找一个满足某种条 ... -
广度优先搜索学习五例之四
2012-10-16 15:26 1166例:输出由数字0,1,2..n ... -
广度优先搜索学习五例之三
2012-10-14 19:19 1504广度优先搜索是以某一节点为出发点,先拜访所有相邻的节点。 ... -
广度优先搜索学习五例之一
2012-10-13 15:27 1674有两种常用的方法可用来搜索图:即深度优先搜索和广度优先搜 ... -
广度优先搜索学习五例之二(JAVA)
2012-10-12 14:32 2131再次强调: 图的广度优先搜索,要遵守以下规则: (0) 选取某 ... -
动态规划算法学习十例之十
2012-10-08 21:00 2279凸多边形最优三角剖分 一凸8边形P的顶点顺时针为{v1 ... -
动态规划算法学习十例之九
2012-10-07 15:50 1112最长单调递增子序列的长度问题 所谓子序列,就是在原序列里删 ...
相关推荐
标题 "动态规划算法学习十例之八" 暗示了我们将探讨动态规划这一重要的算法概念,特别是通过一个具体的例子——Matrix Chain Multiplication(矩阵链乘法)来深入理解。动态规划是一种解决复杂问题的有效方法,它...
在这个“动态规划算法学习十例之七”的主题中,我们将聚焦于一个具体的动态规划问题——最长公共子序列(Longest Common Subsequence,简称LCS)。这个问题在计算机科学中具有很高的实用价值,尤其是在比较和分析...
在这个“动态规划算法学习十例之九”的主题中,我们将聚焦于如何通过DP来解决实际问题。尽管描述部分没有提供具体的实例,但从标题来看,我们可以推测这是一个关于动态规划应用的系列教程的第九个例子。 动态规划的...
在这个主题“动态规划算法学习十例之六”中,我们将探讨如何利用动态规划方法来解决实际问题。博文链接虽然未提供具体内容,但我们可以根据提供的文件名推测讨论的是一个具体的编程实例。 `Main.java`通常是一个...
在这个“动态规划算法学习十例之四”的主题中,我们将专注于背包问题的解决方案。背包问题是一个经典的计算机科学问题,它通常涉及在给定容量的背包中选择物品以最大化总价值。 首先,我们来了解动态规划的基本思想...
在这个"动态规划算法学习十例之二"中,我们很可能会探讨两个具体的动态规划应用:一个可能涉及二项式系数计算,另一个可能是斐波那契数列的求解。下面,我们将深入这两个主题,理解它们背后的动态规划策略。 首先,...
在这个“动态规划算法学习十例之一”的主题中,我们将会探讨动态规划的基本概念和一个具体的实例,通过分析`Test.java`源码来深入理解。 首先,动态规划的核心思想是将一个大问题分解为相互重叠的小问题,并通过...
动态规划是一种重要的算法思想,广泛应用于解决复杂问题的优化,如最短路径、背包问题、最长公共子序列等。在本篇文章中,我们将探讨动态规划的精髓,并通过具体实例进行深入学习。博客链接提供了详细的解析,虽然...
在压缩包中的"近似串匹配问题"文件可能包含了这样的C语言实现,可以作为学习和理解近似串匹配动态规划算法的一个实例。 总结一下,近似串匹配的动态规划算法是一种高效的方法,通过Levenshtein距离或Hamming距离...
三:图论、动态规划算法、综合题专集》是一本专门针对编程竞赛中的重要算法与问题解决策略的书籍。它涵盖了图论、动态规划以及综合题型,这些都是在竞赛中经常遇到并且至关重要的主题。下面将对这三个方面进行详细的...
在课程设计过程中,学生还将学习如何分析动态规划算法的时间复杂度和空间复杂度。例如,大多数动态规划解决方案的时间复杂度为O(n*W),其中n是物品数量,W是背包容量,而空间复杂度通常是O(n*W)或者更优,取决于是否...
动态规划算法以其卓越的能力,成为应对这类问题的首选工具。它通过把复杂问题分解成更小、更易于管理的子问题,以递归的方式进行解决。这种方法不仅效率高,而且在很多情况下比其他算法(如贪婪算法或分治算法)更优...
在实际编程中,理解和掌握动态规划算法对于提高问题解决能力至关重要,因为它能够优雅地处理复杂度高且具有结构重叠的优化问题。在学习动态规划时,推荐阅读如《Introduction to Algorithms》等经典教材,它们深入浅...
标题中提到的是“算法参考资料国际大学生程序设计竞赛例题解3 图论·动态规划算法·综合题专集”。这份资料集中的标题揭示了内容的几个关键点,即它是一份专门为解决算法问题而编写的参考资料,特别针对国际大学生...
**算法动态规划专题** 动态规划(Dynamic Programming,简称DP)是一种在计算机科学中解决最优化问题的算法技术,尤其在解决复杂度较高的多阶段决策问题时表现得尤为出色。它通过将大问题分解为小问题,并存储子...
本文将深入探讨五大基础算法思想:分治、动态规划、贪心、回溯和分支界限,并与数据结构相结合,帮助我们理解和应用这些算法。 一、分治法 分治法是一种将复杂问题分解为较小、独立且相似的子问题的策略,然后对子...
动态规划算法通常包含以下几个步骤: 1. 定义状态:识别问题中的关键状态,它们通常是问题的某个阶段的特性描述。 2. 状态转移方程:建立从一个状态到下一个状态的转换规则,这个方程描述了如何根据先前的状态计算...
"基于岭回归机器学习算法的项目成本预测研究——以A风景园林规划研究院规划设计项目为例.pdf" 本文研究主要集中在基于岭回归机器学习算法的项目成本预测研究,以A风景园林规划研究院规划设计项目为例。该研究的目的...