《国家集训队2007论文集7.袁昕颢《动态树问题》由会员分享，可在线阅读，更多相关《国家集训队2007论文集7.袁昕颢《动态树问题（67页珍藏版）》请在金锄头文库上搜索。
1、Dynamic Trees Problem, Dynamic Trees Problem, and its applicationsand its applications湖南省长郡中学 袁昕颢 xinhaoyuanatgmaildotcomOverviewn动态树问题n给出动态树问题的基本形式.n解决动态树问题n提出新的Rake & Compress方法.n动态树问题的应用n用最大流算法来说明动态树问题的应用.Part I. Dynamic Trees ProblemDynamic Trees Problemn动态树问题(Dynamic Trees Problem) 是图论中一类非常重要的经
2、典问题. 许 多图论算法, 尤其是在线动态算法都将 其作为瓶颈问题.n研究和解决该问题具有很高的理论价值 和实际价值.n什么是动态树问题呢?Dynamic Trees Problemn维护一个包含N个 点的森林, 并且支 持形态和权值信息 的操作.n形态信息Dynamic Trees Problemn维护一个包含N个 点的森林, 并且支 持形态和权值信息 的操作.n形态信息nLink(u,v) 添加边 (u,v)Dynamic Trees Problemn维护一个包含N个 点的森林, 并且支 持形态和权值信息 的操作.n形态信息nLink(u,v) 添加边 (u,v)nCut(u,v) 删除边
3、 (u,v)Dynamic Trees Problemn维护一个包含N个 点的森林, 并且支 持形态和权值信息 的操作.n形态信息nLink(u,v) 添加边 (u,v)nCut(u,v) 删除边 (u,v)nFind(u) 找到u所 在的树.Dynamic Trees Problemn维护一个包含N个 点的森林, 并且支 持形态和权值信息 的操作.n权值信息Dynamic Trees Problemn维护一个包含N个 点的森林, 并且支 持形态和权值信息 的操作.n权值信息n路径操作: 对一条简 单路径上的所有对 象进行操作Dynamic Trees Problemn维护一个包含N个 点的森
4、林, 并且支 持形态和权值信息 的操作.n权值信息n路径操作: 对一条简 单路径上的所有对 象进行操作n树操作: 对一棵树内 的所有对象进行操 作现有结果基本原理Euler TourPath Decompos ingDivide and Conquer相关实现Euler Tour TreesST- Trees1,2(Self Adjust) Top- Trees3,5局限性不支持路 径操作不支持树 权操作常数过大理论补充n对于一个完整的动态树问题, 目前公认 的下界是O(log2N) per operation, 并已 经被上述方法达到.n但是由于巨大的常数因子, 动态树在实 践中并没有发挥应
5、有的作用.n动态树问题仍然没有完美解决, 并且仍 然处在热烈讨论中.Part II. Solving Dynamic Trees ProblemNew Idean在这里, 我向大家介绍一种新的解决动 态树问题的思路. 这种思路简单, 而且, 可以得到效率非常高的具体实现.I. 树, 与其平面刻画.n一棵树的平面刻画, 直观地说就是将一 棵树的点和边画在 平面上. 边与边仅 在顶点处相交.I. 树, 与其平面刻画.n一棵树的平面刻画, 直观地说就是将一 棵树的点和边画在 平面上. 边与边仅 在顶点处相交.n确定一棵树的平面 刻画, 等价于确定 这棵树的Euler Tour.II. 等价映射n事实
6、上, 所有解决 动态树问题的方法, 归根结底都使用等 价映射的基本思想.n即, 将任意形态的 树(原树)映射到度 限制, 深度平均的 新树(像树).III. Rake & Compressn这里介绍一种Rake & Compress5,6方 法.n即将原树映射到一 棵Rake & Compress Trees (Abbr. R&C Trees).nR&C Trees由Rake 节点和Compress 节点组成.1. Rake NodesnRake节点i是原树 中以某节点为根的 有根子树的映射.Root1. Rake NodesnRake节点i是原树 中以某节点为根的 有根子树的映射.n特别地,
7、 如果该节 点仅包含根本身, 那么该Rake节点没 有后继(叶子节点). 否则令Next(i)表示i 所代表的除了根以 外的其它点组成的 集合.Root2. Compress NodesnCompress节点j, 是 原树中以某条路径 为根的有根子树的 映射.se2. Compress NodesnCompress节点j, 是 原树中以某条路径 为根的有根子树的 映射.n特别地, 如果路径 长度为1. 那么该 Compress节点没 有后继. 否则令 Next(j)表示j代表的 路径上的非端点集 合.se3. R&C Treesn对于一个非叶子Rake/Compress节点i, Next(i)
8、非空.n对于每个Next(i)中的元素j. 我们采用如 下方法划分节点i:1 Rake节点的划分n令r表示i的根.rj1 Rake节点的划分n令r表示i的根.n将路径j r作为新的 Compress节点.rj1 Rake节点的划分n令r表示i的根.n将路径j r作为新的 Compress节点.n将j和j的子孙作为新 的Rake节点.rj1 Rake节点的划分n令r表示i的根.n将路径j r作为新的 Compress节点.n将j和j的子孙作为新 的Rake节点.ni中路径j r的左手 方向和右手方向各 为一个新的Rake节 点.rj2 Compress节点的划分n令s,e分别表示i中 路径的头和
9、尾.sej2 Compress节点的划分n令s,e分别表示i中 路径的头和尾.ns j,j e分别成为新 的Compress节点sej2 Compress节点的划分n令s,e分别表示i中 路径的头和尾.ns j,j e分别成为新 的Compress节点nj的其他子孙被划分 成两部分, 分别作 为新的Rake节点.sejR&C Treesn约定, 一个有根树 对应R&C Trees就 是整个树的Rake Node.n这样的分解方式本 身就保证度的限制( 一个节点最多被剖 分出4个子节点)n我们以右图为例， 展示一棵原树如何 被映射到像树。Level 1选取I作为第1层剖分点，原Rake节点被剖分
10、 成4个部分，4个部分分别剖分。Level 2选取B,C,D,L作为第2层剖分点。Level 3选取F,E,G,H,K,J作为第3层剖分点。Final这样，我们就构建出了整个树的R&C Trees 。Randomizedn决定R&C Trees深度的关键因素在于选 择Next(i)中元素的方法.n一个比较好的方法是, 随机选择! n如果等概率的选择Next(i)中的元素, 可 以证明这样的深度下界是(ln2N). 问题 并没有完全解决.n必须采取更为合理的随机策略.Randomizedn对于Rake节点, 仍然采取等概率的方法 选择.n对于Compress节点i, j表示Next(i)中的 元
11、素, 令Weight(j)表示j剩余的子孙个数( 包括j).n现在以Weight(j)作为加权, 令S表示所 有Weight(k)的和, 则j有Weight(j)/S的概 率被选择.Randomized : Master Theoremn可以证明, 通过这样合理的改造, 一个N 的点的树可以被映射到一个期望深度为 O(lnN)的R&C Trees.n基于这种思想, RP-Trees被提出. 事实 上, 这就是Treap7通过R&C思想在任意 树的拓展.n通过这种思想, 我们可以得到均摊, 甚至 是严格深度O(lnN)的算法.小结n相比较于Path Decomposing和Divide & Co
12、nquer, Rake & Compress具有思想 简单, 常数小, 实现复杂度低等特点.nR&C思想最大的特点是, 利用这种思想 可以很方便地将各种平衡二叉树技巧拓 展到任意树形态上去.n为Dynamic Trees Problem 注入了新的 血液.Part III. ApplicationsApplications n网络优化n最大流4 n最小费用流nn动态算法n动态连通性3,8n动态最小生成森林3nn最大流问题n最大流问题是非常经典的图论问题. 经 典的解决算法有最短增广路, 预流推进.n通过改造最短增广路算法并应用动态树 , 可以得到O(NMlnN)的算法. N为点数, M为边数.
13、n经典的最短增广路算法是通过BFS, 每 次在残余网络中找到一条最短S-T增广 路并进行增广.Residual networkResidual network找到最短增广路 S C E T 增广量为3Residual networkResidual network找到最短增广路 S A E T 增广量为8Residual network最大流问题n引理: 只需要O(NM)次增广.n证明: 考察当前最短路的必要边集An所有S T的最短路全部由A中元素组成n|A|Mn每次都找到最短增广路, 增广后A中元 素必有一条边被删除(残余量为0).最大流问题n在S T最短路长度被提高之前不可能有 边从A外加
14、入到A内.nO(M)次增广后S T增广路长度必被提 高. 因此最多执行O(NM)次增广.n综上所述, 引理得证.最大流问题n原始算法的时间复杂度为O(NM2).n令D(x)表示x到T的最短增广路下界.n对于所有残余量0的边u v, 满足 D(u)D(v)+1.n如果D(u)=D(v)+1, 则称u v为有效边.n引理: 全部由有效边组成的到T的路径一定 是最短路径!最大流问题n每次在残余网络中沿着让D(x)递减的有 效边前进. 并不断修正(抬高)D(x). 可以 证明, 该优化方法将寻找最短增广路的 时间降为均摊O(N), 所以需要的总时间 降为O(N2M).n那么, 能不能再次改进呢?最大流
15、问题n一个想法是, 维护有效边子集的生成森林. n如果S, T不在同一棵树内. 令R为S所在树内D 值最小的点(最低点), 如果存在有效边R R, 则执行Link(R,R).n如果此时R没有连出的有效边, 显然D(R)是可 以改进的. 即这个下界是松的, 此时我们抬高 D(R). 并更新有效边集.n当S和T都在同一棵树内时(即最低点为T), 对 树中的S-T路径进行增广.n每次所增广的路都是最短增广路.Residual networkD(x)x黑色边为有效边Residual networkD(x)x红色边为生成森林边Residual networkD(x)x找到一条由当前最低点 A连出的有效边
16、A E 执行Link(A,E)Residual networkD(x)x找到最短增广路 S A E T 增广量为8Residual networkD(x)x增广后A E不再有效 Cut(A,E)Residual networkD(x)x尝试找到从最低点A连 出的边，失败 抬高D(A)并更新有效边Residual networkD(x)x找到一条由当前最低点 S连出的有效边S C 执行Link(S,C)Residual networkD(x)x找到一条由当前最低点 C连出的有效边C E 执行Link(C,E)Residual networkD(x)x找到最短增广路 S C E T 增广量为3Residual networkD(x)x最大流问题n由于流程和最短增广路一样, 故正确性 显然.n现在考察其时间复杂度.最大流问题n前面已经说过, 最多执行O(NM)次
