[电脑基础知识]几种基本算法在树形结构上的应用.ppt

几种基本算法在树形结构上的应用 南京外国语学校 欧阳云 摘要 树形结构是信息学中重要的结构模型之一，有关树形结构的试题在竞赛中也经常出现。鉴于在树形结构上使用动态规划算法已成为近年来信息学竞赛的考察热点，本文将重点围绕动态规划算法在树形结构上的应用，分三个部分进行阐述，首先对树形结构的特点进行简要介绍，然后对几种基本算法在树形结构上的应用举例说明，最后进行总结。 引言 众所周知，树形结构是在信息学竞赛中经常出现的一类结构模型，各类有关树形结构的题目也是屡见不鲜 。 纯粹的树形结构题，因为树形模型较为单一，而没有比较大的难度。 因此，我们经常看到的是在树形结构上，运用一些基本算法解决难度更大的问题。 本文将对此进行一些探索。 树形结构的特点 由于这里主要研究的是树形结构的特点，因此在这里，树的定义和一些基本概念就不赘述了。下面主要阐述一些树形结构的主要特点。 树形结构的特点 在一棵树里，除了根节点以外的所有节点有且只有一个父亲节点，根节点没有父亲节点。除了叶子节点外，所有的节点有一个或多个孩子节点，叶子节点没有孩子节点。 一棵树里任意两个节点之间都有且只有一条通路，如果把任意一节点与其相邻节点之间的通路看作一条无向边的话，那么一棵树里没有环及重边的存在。因此，一棵有N个节点的树恰好有N-1条边。 树形结构的特点 树是具有递归结构的。一个节点即是一棵树，而一棵有孩子节点的树，若其根节点为a节点，则其任意一个孩子节点b，与所有不用通过a节点即可和b相连的节点也构成一棵树，称为以b为根的a的一棵子树。b的任意一棵子树也是a的一棵子树。 如果一棵树是有根的，那么某个节点a的深度d(a)=d(father(a))+1，其中father(a)为a的父亲节点。特别的，d(root)=1。 树形结构的特点 以上即为一些树形结构所具有的特点，在本文的例题中，对于以上几条性质将会有所应用，到时将不再具体阐述。 树形结构的特点 对于一棵树，对于它的遍历一般有两种途径。第一种是深度优先遍历，第二种是宽度优先遍历，这两种遍历方法对于一棵树进行遍历后，会得到不同的遍历顺序。在一般的使用中，这两种遍历都是十分有用的。对于深度优先遍历，我们可以写出如下的伪代码： 树形结构的特点 由此我们可以看出，对于一棵树进行深度优先遍历后，每个节点的孩子节点的时间戳都是小于当前节点的，在后面的题目中，我们会对于这一性质进行一些应用。 树形结构的特点 而对于宽度优先遍历，我们可以写出如下的伪代码： 树形结构的特点 由此可以看出，对于一棵树进行宽度优先遍历后，每个节点的孩子节点的时间戳都是小于当前节点的，而且满足深度越小的节点，它的时间戳越小。在后面的题目中，我们也会对这一性质进行一些应用。 几种基本算法在树形结构上的应用 下面，我便向大家介绍几种基本算法在树形结构上的应用。 动态规划在树形结构上的应用 近几年的信息学竞赛中，在树形结构上使用动态规划的题目屡见不鲜，而且有延续之趋势。由于对简单的动态规划研究的人越来越多，所以在树形结构上的动态规划题越来越多。这种动态规划题具有数据量大，编写起来比较复杂的特点，尤其是题目变化的余地很大，往往会让参赛的选手措手不及。为了有效解决这一问题，我们必须紧紧抓住这种动态规划的显著特点，如利用树形结构中，没有环存在，每个点只有一个父亲节点等特点，设计高效、正确的算法。 动态规划在树形结构上的应用 使用动态规划算法时，必须满足以下几个条件： 整个问题的求解可以划分为若干个阶段的一系列决策过程。 每个阶段有若干可能状态。 一个决策将你从一个阶段的一种状态带到下一个阶段的某种状态。 在任一个阶段，最佳的决策序列和该阶段以后的决策无关。 各阶段状态之间的转换有明确定义的费用。 动态规划在树形结构上的应用 而在树形结构上使用动态规划时，自然也必须满足以上的几个条件。但具体怎么才能让动态规划在树形结构下有用武之地呢？下面便举几个例子来做简单的说明： 例题1：Cow Marathon (USACO FEB04数据加强版) 在听说了传染病在美国的快速传播后，FJ希望他的奶牛们能得到更多的锻炼，因此他决定创建一个马拉松比赛来让他的奶牛们锻炼身体。FJ的地图中有很多的农场，农场之间有一些路连接它们。这次的马拉松行程将会包含一对农场以及这两个农场之间的所有道路。由于FJ希望他的奶牛们能得到尽可能多的锻炼，所以他希望找到两个在地图上相隔最远的农场作为马拉松行程中的那一对农场。现在他希望你能帮助他找到这个最远的距离的大小。（这里要注意的是，FJ的地图是很特殊的，在这个图上，任意两点间有且只有一条通路可以互相到达） 数据范围： N为农场数，1=N=100000 例题1：Cow M