动态树问题及其应用.ppt

《动态树问题及其应用.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、DynamicTreesProblem,anditsapplications湖南省长郡中学袁昕颢xinhaoyuan[at]gmail[dot]comOverview动态树问题给出动态树问题的基本形式.解决动态树问题提出新的Rake&Compress方法.动态树问题的应用用最大流算法来说明动态树问题的应用.PartI.DynamicTreesProblemDynamicTreesProblem动态树问题(DynamicTreesProblem)是图论中一类非常重要的经典问题.许多图论算法,尤其是在线动

2、态算法都将其作为瓶颈问题.研究和解决该问题具有很高的理论价值和实际价值.什么是动态树问题呢?DynamicTreesProblem维护一个包含N个点的森林,并且支持形态和权值信息的操作.形态信息DynamicTreesProblem维护一个包含N个点的森林,并且支持形态和权值信息的操作.形态信息Link(u,v)–添加边(u,v)DynamicTreesProblem维护一个包含N个点的森林,并且支持形态和权值信息的操作.形态信息Link(u,v)–添加边(u,v)Cut(u,v)–删除边(u,v)Dy

3、namicTreesProblem维护一个包含N个点的森林,并且支持形态和权值信息的操作.形态信息Link(u,v)–添加边(u,v)Cut(u,v)–删除边(u,v)Find(u)–找到u所在的树.DynamicTreesProblem维护一个包含N个点的森林,并且支持形态和权值信息的操作.权值信息DynamicTreesProblem维护一个包含N个点的森林,并且支持形态和权值信息的操作.权值信息路径操作:对一条简单路径上的所有对象进行操作DynamicTreesProblem维护一个包含N个点的森

4、林,并且支持形态和权值信息的操作.权值信息路径操作:对一条简单路径上的所有对象进行操作树操作:对一棵树内的所有对象进行操作现有结果基本原理EulerTourPathDecomposingDivideandConquer相关实现EulerTourTreesST-Trees[1,2](SelfAdjust)Top-Trees[3,5]局限性不支持路径操作不支持树权操作常数过大理论补充对于一个完整的动态树问题,目前公认的下界是O(log2N)peroperation,并已经被上述方法达到.但是由于巨大的常数因

5、子,动态树在实践中并没有发挥应有的作用.动态树问题仍然没有完美解决,并且仍然处在热烈讨论中.PartII.SolvingDynamicTreesProblemNewIdea在这里,我向大家介绍一种新的解决动态树问题的思路.这种思路简单,而且,可以得到效率非常高的具体实现.I.树,与其平面刻画.一棵树的平面刻画,直观地说就是将一棵树的点和边画在平面上.边与边仅在顶点处相交.I.树,与其平面刻画.一棵树的平面刻画,直观地说就是将一棵树的点和边画在平面上.边与边仅在顶点处相交.确定一棵树的平面刻画,等价于确定

6、这棵树的EulerTour.II.等价映射事实上,所有解决动态树问题的方法,归根结底都使用等价映射的基本思想.即,将任意形态的树(原树)映射到度限制,深度平均的新树(像树).III.Rake&Compress这里介绍一种Rake&Compress[5,6]方法.即将原树映射到一棵Rake&CompressTrees(Abbr.R&CTrees).R&CTrees由Rake节点和Compress节点组成.1.RakeNodesRake节点i是原树中以某节点为根的有根子树的映射.Root1.RakeNode

7、sRake节点i是原树中以某节点为根的有根子树的映射.特别地,如果该节点仅包含根本身,那么该Rake节点没有后继(叶子节点).否则令Next(i)表示i所代表的除了根以外的其它点组成的集合.Root2.CompressNodesCompress节点j,是原树中以某条路径为根的有根子树的映射.se2.CompressNodesCompress节点j,是原树中以某条路径为根的有根子树的映射.特别地,如果路径长度为1.那么该Compress节点没有后继.否则令Next(j)表示j代表的路径上的非端点集合.se

8、3.R&CTrees对于一个非叶子Rake/Compress节点i,Next(i)非空.对于每个Next(i)中的元素j.我们采用如下方法划分节点i:1’Rake节点的划分令r表示i的根.rj1’Rake节点的划分令r表示i的根.将路径jr作为新的Compress节点.rj1’Rake节点的划分令r表示i的根.将路径jr作为新的Compress节点.将j和j的子孙作为新的Rake节点.rj1’Rake节点的划分令r表示i的根.将路径j