袁昕颢动态树问题及其应用.ppt
《袁昕颢动态树问题及其应用.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个点的森林, 并且支持形态和权值
3、信息的操作. 形态信息 Link(u,v) 添加边(u,v) Cut(u,v) 删除边(u,v) Find(u) 找到u所在的树.,Dynamic Trees Problem,维护一个包含N个点的森林, 并且支持形态和权值信息的操作. 权值信息,Dynamic Trees Problem,维护一个包含N个点的森林, 并且支持形态和权值信息的操作. 权值信息 路径操作: 对一条简单路径上的所有对象进行操作,Dynamic Trees Problem,维护一个包含N个点的森林, 并且支持形态和权值信息的操作. 权值信息 路径操作: 对一条简单路径上的所有对象进行操作 树操作: 对一棵树内的所有对象
4、进行操作,现有结果,理论补充,对于一个完整的动态树问题, 目前公认的下界是O(log2N) per 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. Rak
6、e Nodes,Rake节点i是原树中以某节点为根的有根子树的映射.,Root,1. Rake Nodes,Rake节点i是原树中以某节点为根的有根子树的映射. 特别地, 如果该节点仅包含根本身, 那么该Rake节点没有后继(叶子节点). 否则令Next(i)表示i所代表的除了根以外的其它点组成的集合.,Root,2. Compress Nodes,Compress节点j, 是原树中以某条路径为根的有根子树的映射.,s,e,2. Compress Nodes,Compress节点j, 是原树中以某条路径为根的有根子树的映射. 特别地, 如果路径长度为1. 那么该Compress节点没有后继.
7、否则令Next(j)表示j代表的路径上的非端点集合.,s,e,3. R&C Trees,对于一个非叶子Rake/Compress节点i, Next(i)非空. 对于每个Next(i)中的元素j. 我们采用如下方法划分节点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的子孙作为
8、新的Rake节点. i中路径jr的左手方向和右手方向各为一个新的Rake节点.,r,j,2 Compress节点的划分,令s,e分别表示i中路径的头和尾.,s,e,j,2 Compress节点的划分,令s,e分别表示i中路径的头和尾. 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. 这样的分解方式本身就保证度的限制
9、(一个节点最多被剖分出4个子节点) 我们以右图为例,展示一棵原树如何被映射到像树。,Level 1,选取I作为第1层剖分点,原Rake节点被剖分成4个部分,4个部分分别剖分。,Level 2,选取B,C,D,L作为第2层剖分点。,Level 3,选取F,E,G,H,K,J作为第3层剖分点。,Final,这样,我们就构建出了整个树的R&C Trees。,Randomized,决定R&C Trees深度的关键因素在于选择Next(i)中元素的方法. 一个比较好的方法是, 随机选择! 如果等概率的选择Next(i)中的元素, 可以证明这样的深度下界是(ln2N). 问题并没有完全解决. 必须采取更为
10、合理的随机策略.,Randomized,对于Rake节点, 仍然采取等概率的方法选择. 对于Compress节点i, j表示Next(i)中的元素, 令Weight(j)表示j剩余的子孙个数(包括j). 现在以Weight(j)作为加权, 令S表示所有Weight(k)的和, 则j有Weight(j)/S的概率被选择.,Randomized : Master Theorem,可以证明, 通过这样合理的改造, 一个N的点的树可以被映射到一个期望深度为O(lnN)的R&C Trees. 基于这种思想, RP-Trees被提出. 事实上, 这就是Treap7通过R&C思想在任意树的拓展. 通过这种思
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 袁昕颢 动态 问题 及其 应用
链接地址:https://www.31doc.com/p-3304555.html