文档介绍：竞赛数据结构数学分析动态程序设计搜索网络流累计全国奥林匹克信息学竞赛分区联赛233  8全国奥林匹克信息学竞赛2121 6国际奥林匹克信息学竞赛中国组队赛12111`6国际奥林匹克信息学竞赛41 1 6累计9763126       一、几个知识点回顾(一)动态规划1、动态程序设计的定义:动态程序设计是一个“多阶段最优化决策的过程”。即由初始状态开始,通过对中间阶段决策的选择,达到结束状态。这些决策形成了一个决策序列,同时确定了完成整个过程的一条最优的活动路线()。、动态程序设计的几个名词:⑴状态(State):表示事物的性质,是描述“动态规划”中的“单元”的量。亦是每一阶段求解过程的出发点。⑵阶段(Stage):阶段是一些性质相近,可以同时处理的状态集合,或者说,阶段只是标识那些处理方法相同、处理顺序无关的状态。通常,一个问题可以由处理的先后次序划分为几个阶段。一个阶段既可以包含多个状态,也可以只包含一个状态。阶段与状态的关系很类似分子与原子的关系阶段的顺序是确定的,不可以调换任两个阶段的顺序阶段i中某状态的取值仅与阶段i-1中与之相关的所有状态有关,且只对阶段i+1中与之相关的状态取值产生影响⑶决策(Decision):每个阶段做出的某种选择性的行动,是程序所需要完成的选择。⑷状态转移方程:是前一个阶段的状态转移到后一个的状态的演变规律,是关于两个相邻阶段状态变化的方程,是“动态规划”的中心。设fk(i)—k阶段状态i的最优权值,即初始状态至状态i的最优代价  由上可见,所谓最优化决策是指在k-1阶段的所有状态中,究竟选择哪个状态j可使得fk(i)成立。总体上来说,一个“动态规划”算法应该包含上面提到的几种基本关系与属性。由于动态程序设计是按照阶段的顺序,直接在子问题最优解的基础上计算的,“不做已经做过的工作”,因此其效率比搜索法好得多。只要问题的计算过程呈阶段性,且可找到状态转移方程,我们宁可摒弃传统的搜索而采用动态程序设计方法。(二)哈希表(HashTable)根据关健码值直接访问。把关键码映射到表中的一个位置来访问记录的过程。这个映射函数叫做哈希函数,在存放记录的表叫做哈希表。也就是说,将所有元素存储在一张表中,每一个元素具有一个哈希函数,按照如下两种方式给同一个哈希函数值的所有元素分配多个空间():,可以经过较少的次数得到所查的元素,提高查询的时间效率。考虑哈希函数的因素有:计算哈希函数所需时间;关键字的长度;哈希表的大小;关键字的分布情况;记录的查找频率;(三)、最大排序二叉树(二叉搜索树、二叉检索树、二分检索树)是指它要么是一棵空树,要么它的左子树的所有结点比根结点小,右子树的所有结点比树根结点大,它的左子树和右子树分别是一棵排序二叉树。最大排序二叉树是指在所有的排序二叉树中节点最多的一棵树。(四)。当函数w[i,j]满足时,称w满足四边形不等式。在动态规划中被运用于证明决策的单调性。(五)平衡二叉树二叉搜索树可以实现任何一种基本的动态集合操作,但当树的高度时,这些操作性能可能变差,即不能保证在最坏的情况下动态集合操作的时间为O(lgn)。这样情况是因为二叉树可能变得不平衡。用一组规则让二叉树平衡起来,例如,红-黑树确保了没有一条路径会比任何其他路径长到两倍,因而基本上是平衡的。AVL树应用平衡化旋转规则来完成指针结构的修改。(六)博弈树、博弈树的定义:如果将初始状态作为根结点,把从初始状态的每一个可能棋步出发,进行一轮游戏后得到的所有子状态作为根结点的孩子结点;然后从这些新状态出发进行下一轮游戏,得到的又一批子状态作为新状态的孩子结点,…,依次类推,就可以根据游戏规则产生一棵包罗了各种可能状态变化的树****惯上称为博弈树()。、博弈树的特征:1、奇数层的状态由先行方进行操作,偶数层的状态由后行方进行操作;2、从根结点到当前状态的走步序列(路径)表示了双方依次轮流走过的棋步;3、叶子是游戏的终止状态(即状态数为0或先前确定了取珠的洞口)。若叶子处在奇数层,后行方赢;若叶子处在偶数层,先行方赢;4、在对弈中,双方都想赢,都会采取取胜的策略。3、构造博弈树的基本思想:我们在博弈树的每个结点上标一个值F,由这个值来确定操作方最佳的走法。不妨认为,F越大对先行方越有利,奇数层结点总是挑选使得F值最大的方案走;而偶数层结点则恰好相反。由于子结点是由父结点推出来的,故父结点的F值与其所有子结点的F值有一定的关系。另一方面,游戏愈接近结束愈便于分析,也便于计算F值。我们可从叶子结点出发,往上倒推每个结点的F值,直至初始状态的F值为止。整棵博弈树建立之后,便产生出取胜的策略。在过去