《动态树问题及其应.ppt》由会员分享，可在线阅读，更多相关《动态树问题及其应.ppt（73页珍藏版）》请在三一办公上搜索。
1、Dynamic Trees Problem,and its applications,湖南省长郡中学 袁昕颢xinhaoyuanatgmaildotcom,Overview,动态树问题给出动态树问题的基本形式.解决动态树问题提出新的Rake&Compress方法.动态树问题的应用用最大流算法来说明动态树问题的应用.,Part I.Dynamic Trees Problem,Dynamic Trees Problem,动态树问题(Dynamic Trees Problem)是图论中一类非常重要的经典问题.许多图论算法,尤其是在线动态算法都将其作为瓶颈问题.研究和解决该问题具有很高的理论价值和实际
2、价值.什么是动态树问题呢?,Dynamic Trees Problem,维护一个包含N个点的森林,并且支持形态和权值信息的操作.形态信息,Dynamic Trees Problem,维护一个包含N个点的森林,并且支持形态和权值信息的操作.形态信息Link(u,v)添加边(u,v),Dynamic Trees Problem,维护一个包含N个点的森林,并且支持形态和权值信息的操作.形态信息Link(u,v)添加边(u,v)Cut(u,v)删除边(u,v),Dynamic Trees Problem,维护一个包含N个点的森林,并且支持形态和权值信息的操作.形态信息Link(u,v)添加边(u,v)
3、Cut(u,v)删除边(u,v)Find(u)找到u所在的树.,Dynamic Trees Problem,维护一个包含N个点的森林,并且支持形态和权值信息的操作.权值信息,Dynamic Trees Problem,维护一个包含N个点的森林,并且支持形态和权值信息的操作.权值信息路径操作:对一条简单路径上的所有对象进行操作,Dynamic Trees Problem,维护一个包含N个点的森林,并且支持形态和权值信息的操作.权值信息路径操作:对一条简单路径上的所有对象进行操作树操作:对一棵树内的所有对象进行操作,现有结果,理论补充,对于一个完整的动态树问题,目前公认的下界是O(log2N)pe
4、r operation,并已经被上述方法达到.但是由于巨大的常数因子,动态树在实践中并没有发挥应有的作用.动态树问题仍然没有完美解决,并且仍然处在热烈讨论中.,Part II.Solving Dynamic Trees Problem,New Idea,在这里,我向大家介绍一种新的解决动态树问题的思路.这种思路简单,而且,可以得到效率非常高的具体实现.,I.树,与其平面刻画.,一棵树的平面刻画,直观地说就是将一棵树的点和边画在平面上.边与边仅在顶点处相交.,I.树,与其平面刻画.,一棵树的平面刻画,直观地说就是将一棵树的点和边画在平面上.边与边仅在顶点处相交.确定一棵树的平面刻画,等价于确定这
5、棵树的Euler Tour.,II.等价映射,事实上,所有解决动态树问题的方法,归根结底都使用等价映射的基本思想.即,将任意形态的树(原树)映射到度限制,深度平均的新树(像树).,III.Rake&Compress,这里介绍一种Rake&Compress5,6方法.即将原树映射到一棵Rake&Compress Trees(Abbr.R&C Trees).R&C Trees由Rake节点和Compress节点组成.,1.Rake Nodes,Rake节点i是原树中以某节点为根的有根子树的映射.,Root,1.Rake Nodes,Rake节点i是原树中以某节点为根的有根子树的映射.特别地,如果该
6、节点仅包含根本身,那么该Rake节点没有后继(叶子节点).否则令Next(i)表示i所代表的除了根以外的其它点组成的集合.,Root,2.Compress Nodes,Compress节点j,是原树中以某条路径为根的有根子树的映射.,s,e,2.Compress Nodes,Compress节点j,是原树中以某条路径为根的有根子树的映射.特别地,如果路径长度为1.那么该Compress节点没有后继.否则令Next(j)表示j代表的路径上的非端点集合.,s,e,3.R&C Trees,对于一个非叶子Rake/Compress节点i,Next(i)非空.对于每个Next(i)中的元素j.我们采用如
7、下方法划分节点i:,1 Rake节点的划分,令r表示i的根.,r,j,1 Rake节点的划分,令r表示i的根.将路径jr作为新的Compress节点.,r,j,1 Rake节点的划分,令r表示i的根.将路径jr作为新的Compress节点.将j和j的子孙作为新的Rake节点.,r,j,1 Rake节点的划分,令r表示i的根.将路径jr作为新的Compress节点.将j和j的子孙作为新的Rake节点.i中路径jr的左手方向和右手方向各为一个新的Rake节点.,r,j,2 Compress节点的划分,令s,e分别表示i中路径的头和尾.,s,e,j,2 Compress节点的划分,令s,e分别表示i
8、中路径的头和尾.sj,je分别成为新的Compress节点,s,e,j,2 Compress节点的划分,令s,e分别表示i中路径的头和尾.sj,je分别成为新的Compress节点j的其他子孙被划分成两部分,分别作为新的Rake节点.,s,e,j,R&C Trees,约定,一个有根树对应R&C Trees就是整个树的Rake Node.这样的分解方式本身就保证度的限制(一个节点最多被剖分出4个子节点)我们以右图为例，展示一棵原树如何被映射到像树。,Level 1,选取I作为第1层剖分点，原Rake节点被剖分成4个部分，4个部分分别剖分。,Level 2,选取B,C,D,L作为第2层剖分点。,L
9、evel 3,选取F,E,G,H,K,J作为第3层剖分点。,Final,这样，我们就构建出了整个树的R&C Trees。,Randomized,决定R&C Trees深度的关键因素在于选择Next(i)中元素的方法.一个比较好的方法是,随机选择!如果等概率的选择Next(i)中的元素,可以证明这样的深度下界是(ln2N).问题并没有完全解决.必须采取更为合理的随机策略.,Randomized,对于Rake节点,仍然采取等概率的方法选择.对于Compress节点i,j表示Next(i)中的元素,令Weight(j)表示j剩余的子孙个数(包括j).现在以Weight(j)作为加权,令S表示所有We
10、ight(k)的和,则j有Weight(j)/S的概率被选择.,Randomized:Master Theorem,可以证明,通过这样合理的改造,一个N的点的树可以被映射到一个期望深度为O(lnN)的R&C Trees.基于这种思想,RP-Trees被提出.事实上,这就是Treap7通过R&C思想在任意树的拓展.通过这种思想,我们可以得到均摊,甚至是严格深度O(lnN)的算法.,小结,相比较于Path Decomposing和Divide&Conquer,Rake&Compress具有思想简单,常数小,实现复杂度低等特点.R&C思想最大的特点是,利用这种思想可以很方便地将各种平衡二叉树技巧拓展
11、到任意树形态上去.为Dynamic Trees Problem 注入了新的血液.,Part III.Applications,Applications,网络优化最大流4 最小费用流动态算法动态连通性3,8动态最小生成森林3,最大流问题,最大流问题是非常经典的图论问题.经典的解决算法有最短增广路,预流推进.通过改造最短增广路算法并应用动态树,可以得到O(NMlnN)的算法.N为点数,M为边数.经典的最短增广路算法是通过BFS,每次在残余网络中找到一条最短S-T增广路并进行增广.,Residual network,Residual network,找到最短增广路SC E T增广量为3,Residu
12、al network,Residual network,找到最短增广路SA E T增广量为8,Residual network,最大流问题,引理:只需要O(NM)次增广.证明:考察当前最短路的必要边集A所有ST的最短路全部由A中元素组成|A|M每次都找到最短增广路,增广后A中元素必有一条边被删除(残余量为0).,最大流问题,在ST最短路长度被提高之前不可能有边从A外加入到A内.O(M)次增广后ST增广路长度必被提高.因此最多执行O(NM)次增广.综上所述,引理得证.,最大流问题,原始算法的时间复杂度为O(NM2).令D(x)表示x到T的最短增广路下界.对于所有残余量0的边uv,满足D(u)D(
13、v)+1.如果D(u)=D(v)+1,则称uv为有效边.引理:全部由有效边组成的到T的路径一定是最短路径!,最大流问题,每次在残余网络中沿着让D(x)递减的有效边前进.并不断修正(抬高)D(x).可以证明,该优化方法将寻找最短增广路的时间降为均摊O(N),所以需要的总时间降为O(N2M).那么,能不能再次改进呢?,最大流问题,一个想法是,维护有效边子集的生成森林.如果S,T不在同一棵树内.令R为S所在树内D值最小的点(最低点),如果存在有效边RR,则执行Link(R,R).如果此时R没有连出的有效边,显然D(R)是可以改进的.即这个下界是松的,此时我们抬高D(R).并更新有效边集.当S和T都在
14、同一棵树内时(即最低点为T),对树中的S-T路径进行增广.每次所增广的路都是最短增广路.,Residual network,黑色边为有效边,Residual network,红色边为生成森林边,Residual network,找到一条由当前最低点A连出的有效边AE执行Link(A,E),Residual network,找到最短增广路SAET增广量为8,Residual network,增广后AE不再有效Cut(A,E),Residual network,尝试找到从最低点A连出的边，失败抬高D(A)并更新有效边,Residual network,找到一条由当前最低点S连出的有效边SC执行Li
15、nk(S,C),Residual network,找到一条由当前最低点C连出的有效边CE执行Link(C,E),Residual network,找到最短增广路SCET增广量为3,Residual network,最大流问题,由于流程和最短增广路一样,故正确性显然.现在考察其时间复杂度.,最大流问题,前面已经说过,最多执行O(NM)次增广,所以在增广上的总时间为O(NMlnN).因为0D(x)N,所以最多执行O(NM)次Cut操作.因此花费在Cut上的总时间为O(NMlnN).又因为在一个点的D值被抬高之前,每个点均摊被Link过1次.综上所述,总的时间复杂度为O(NMlnN),时间复杂度,时
16、间复杂度,时间复杂度,小结,使用动态树问题来优化算法的关键是解决瓶颈问题.在本例中,我们将复杂度摊平到了每一种操作中.使得总的时间复杂度获得了质的飞跃.其实,不仅仅是最大流算法,网络优化的很多算法都可以使用动态树来优化,并得到很好的理论复杂度.,总结,研究动态树问题是非常有价值的,研究它可以加深对图论的理解.其解决方法使用的技巧亦非常具有启发性.更何况其问题本身又是那么美妙!对于一个复杂的经典问题,我们不应仅仅满足于“知道”或者“学会”,更需要融会贯通.这对我们无论是日常学习或者竞赛活动都是非常有好处的.,References,1 Daniel D.Sleator,Robert Endre T
17、arjan,A data structure for dynamic trees,Journal of Computer and System Sciences,v.26 n.3,p.362-391,June 1983.2 Daniel Dominic Sleator,Robert Endre Tarjan,Self-adjusting binary search trees,Journal of the ACM(JACM),v.32 n.3,p.652-686,July 19853 S.Alstrup,J.Holm,K.de Lichtenberg,and M.Thorup.Minimizi
18、ng diameters of dynamic trees.In Proceedings of the 24th International Colloquium on Automata,Languages and Programming,pages 270-280,1997.4 Ahujia,R.K.Dynamic Trees Implementations.Network Flows:Theory,Algorithms,and Applications,p.265-273.5 R.Tarjan and R.Werneck.Self-adjusting top trees.In Procee
19、dings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms(SODA),2005.6 Umut A.Acar,Guy E.Blelloch,Jorge L.Vittes,Separating Structure from Data in Dynamic Trees.7 C.R.Aragon,R.G.Seidel,Randomized Search Trees,Proc.30th Ann.IEEE Symposium on Foundations of Computer Science,pp.540-545,October 1989.8 周源,Dynamic Connectivity研究报告,CTSC2005作业-研究报告.,Thank you!,Questions are welcome!,Rake&Compress思想,Rake&Compress思想最初在5,6被提出.本文中提出的R&C Trees的概念亦相似于引用中提及.并在此之上加上了自己的理解.其随机化的解决方案,是在对Rake&Compress思想的探索中领悟出来的.且不说原创,至少是独立思考的成果.目前我没有在任何文献中找到详细的类似资料.,
