算法合集之《分治算法在树的路径问题中的应用》.ppt

上传人:zhu****ei 文档编号:3501678 上传时间:2019-12-16 格式:PPT 页数:50 大小:391KB
返回 下载 相关 举报
算法合集之《分治算法在树的路径问题中的应用》.ppt_第1页
第1页 / 共50页
算法合集之《分治算法在树的路径问题中的应用》.ppt_第2页
第2页 / 共50页
算法合集之《分治算法在树的路径问题中的应用》.ppt_第3页
第3页 / 共50页
点击查看更多>>
资源描述
分治算法在树的路径问题中的应用,长沙市雅礼中学漆子超,树的路径问题,论文内容,一、树的分治算法,树的分治的两种常见形式:基于点的分治基于边的分治,二、树的路径剖分算法,三、树的分治算法的进一步探讨,如何改进基于边的分治的时间复杂度,归纳为基于链的分治,一、树的分治算法,树的分治算法是分治思想在树型结构上的体现。,两种常见的形式,基于点的分治,两种常见的形式,基于点的分治,1.选取一个点将无根树转为有根树,2.递归处理每一颗以根结点的儿子为根的子树,两种常见的形式,基于边的分治,两种常见的形式,基于边的分治,1.在树中选取一条边,2.将原有的树分成两棵不相交的树,递归处理。,效率分析,可以证明在基于点的分治中,如果每次都选取树的重心,那么至多递归O(LogN)次。,基于边的分治最坏情况下递归次数为O(N)。,【例一】树中点对统计,给定一棵N个结点的带权树。定义dist(u,v)=u,v两点间的路径长度,路径的长度定义为路径上所有边的权和。给定一个K,如果对于不同的两个结点a,b,如果满足dist(a,b)K,则称(a,b)为合法点对。求合法点对个数。,N10000,K109,一条路径:,1.过根节点,2.在一颗子树内,?,树中点对统计,记D(i)表示节点i到根节点路径的长度,Answer=满足D(i)+D(j)K的(i,j)个数i,j属于不同的子树,O(NlogN),树中点对统计,时间复杂度分析,每层的时间复杂度不超过O(NlogN),最多递归O(logN)次,O(Nlog2N),二、路径剖分算法,轻重边路径剖分,将树中的边分为两类:轻边和重边。,记Size(U)表示以U为根的子树的结点个数。,令V为U的儿子中Size(V)最大的一个,那么我们称边(U,V)为重边,其余边为轻边。,轻重边路径剖分,我们称某条路径为重路径,当且仅当它全部由重边组成。那么对于每个点到根的路径上都不超过O(logN)条轻边和O(logN)条重路径。,我们称某条路径为重路径,当且仅当它全部由重边组成。那么对于每个点到根的路径上都不超过O(logN)条轻边和O(logN)条重路径。,路径剖分算法常用来高效的维护点到根的路径,Spoj的Qtree,Astar2008的黑白树,【例二】QueryOnaTree,给定一棵包含N个结点的树,每个节点要么是黑色,要么是白色。要求模拟两种操作:1)改变某个结点的颜色。2)询问最远的两个黑色结点之间的距离。,数据范围:N100000,边权绝对值不超过1000,此题出自2007年浙江省选,但此题中树的边权可能为负,无法使用括号序列。,另寻他法,路径剖分算法,这道题的算法似乎与路径剖分毫无关系,那么我们是否能用路径剖分算法解决此题呢?,路径剖分与树的分治的联系,一棵树及其剖分,路径剖分与树的分治的联系,路径剖分每次删除了一条链,所以路径剖分算法可以看做是基于链的分治,按照点到根结点路径上的轻边个数分层摆放。,递归树!,QueryOnaTree,将路径剖分理解成基于链的分治后,我们可以用类似基于点的分治的方法将路径分类。,1.与链有重合部分,2.与链没有重合部分,QueryOnaTree,我们的目标就是要求出满足与此链的重合部分在1,N的路径的最大长度。,我们可以用线段树解决这个问题。,QueryOnaTree,记D(i)表示第i个结点至子树内某个黑色结点的路径中长度的最大值。Dist(i,j)表示链上的第i个点到第j个点的距离。,QueryOnaTree,对于线段树中的一个区间L,R,我们需要记录下面三个量:,=与此链的重合部分在L,R的路径的最大长度,L,R,L,R,QueryOnaTree,L,R,L,R,L,R,设区间L,R的结点编号为P,Lc,Rc分别表示P的左右两个儿子,区间L,Mid和Mid+1,R。我们可以得到如下转移:,QueryOnaTree,L,R,L,R,L,R,设区间L,R的结点编号为P,Lc,Rc分别表示P的左右两个儿子,区间L,Mid和Mid+1,R。我们可以得到如下转移:,QueryOnaTree,Opt,Opt,L,R,Opt,L,R,设区间L,R的结点编号为P,Lc,Rc分别表示P的左右两个儿子,区间L,Mid和Mid+1,R。我们可以得到如下转移:,QueryOnaTree,注意到Dist(i,j)=Dist(1,j)Dist(1,i),O(1),QueryOnaTree,对于边界情况L,L,MaxL=D(L)MaxR=D(L)Opt=,D2(i)表示第i个结点至子树内某个黑色结点的路径中长度的次大值。,问题只剩下如何维护D和D2的值,QueryOnaTree,该点的儿子到某个黑点路径的最大长度,链的头结点到某个黑点路径的最大长度,!,这正是我们前面已经维护了的量MaxL,一个点向下至某个黑色结点的路径,QueryOnaTree,我们可以使用堆来维护一个点向下至某个黑色结点的路径长度集合,O(1),时间复杂度分析,询问操作:我们使用堆来存贮每条链的最优结果,修改操作:修改一个点最多影响O(logN)条链,对于每条链我们需要修改堆和线段树,O(logN),O(1),O(log2N),路径剖分,AC,三、树的分治算法的进一步探讨,基于点的分治,删除一个点后树的个数太多,加大了设计高效算法的难度,基于边的分治,删除一条边后仅有两棵树,最坏的时间复杂度限制了该算法的应用,改进!,如何改进基于边的分治的时间复杂度,改变选择边的方法?,X,改变树的结构!,无论选择哪条边,结果都是一样的,如何改进基于边的分治的时间复杂度,回想上题,题目所关注的对象是两个黑点之间的距离,这就提醒我们可以在不影响树中黑色结点之间的距离的前提下加入白色结点,如何改进基于边的分治的时间复杂度,通过对每个结点到其儿子的路径中加入了白色结点,使之成为了类似线段树的结构。,叶节点为N的线段树共有2N个结点,所以含有N个结点的树转化后所得的新树最多包含2N个结点。,每个点的度至多为3,如何改进基于边的分治的时间复杂度,定理:如果一棵包含N个结点的树中每个点的度均不大于D,那么存在一条边,使得分出的两棵子树的结点个数在N/(D+1),N*D/(D+1)。,改进后的算法最坏情况下递归深度为O(LogN),使用基于边的分治解决上题,一条路径:,1.过中心边,2.在一颗子树内,1.过中心边,使用基于边的分治解决上题,记录两个根结点到其子树内某个黑色结点的路径的最大长度,最优路径,修改O(logN)询问O(1),时间复杂度分析,询问操作:对每颗树都记录其两个子树的最优值,修改操作:一个点最多属于O(logN)棵树,对于每棵树我们需要修改堆,O(logN),O(1),O(log2N),我们达到了与使用路径剖分同阶的时间复杂度。,算法更加简单,总结,1.算法的常数:基于链的分治基于点的分治N/2,那么我们考虑V作为根结点的情况,记Size(X)表示此时以X为根的子树的结点个数。,定理:存在一个点使得分出的子树的结点个数均不大于N/2,证明:,如图。对于A部分,显然Size(Ti)Size(V)对于B部分,Size(U)=N-Size(V)1时,我们设最优方案为边(U,V),且以U,V为根的两棵子树的结点个数分别为S和N-S,不妨设SN-S。,最优方案指选取一条边使得删除这条边后所分离出来的两棵子树的结点个数较大值最小。设X为U的儿子中以X为根的子树的结点个数最大的一个,我们考虑另一种方案(X,U)。设除去边(X,U)后以X为根的子树结点个数为P,显然P(S-1)/(D-1),由于PS且边(U,V)是最优方案,所以N-PS,与P(S-1)/(D-1)联立可得S(D-1)N+1)/D,又ND+1,所以SN*D/(D+1)。证毕,
展开阅读全文
相关资源
正为您匹配相似的精品文档
相关搜索

最新文档


当前位置:首页 > 图纸专区 > 课件教案


copyright@ 2023-2025  zhuangpeitu.com 装配图网版权所有   联系电话:18123376007

备案号:ICP2024067431-1 川公网安备51140202000466号


本站为文档C2C交易模式,即用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。装配图网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知装配图网,我们立即给予删除!