※ 引述《FRAXIS (喔喔)》之铭言： : : 推 DJWS: 能不能推荐几篇centroid/spine decomposition的教学资料? 03/02 08:14 就我有限的理解，我说明一下 spine decomposition ，大家可以讨论。 首先考虑一个简单的问题 输入： 一条 n 个点的路径，边上有权重及长度（可正可负），以及一数字 U 。 输出： 长度和小於 U 子路径中，最大的权重和。 这问题跟 maximum sum subarray 很类似，只是差在长度不是 uniform 。 考虑两种 divide and conquer 演算法。 1. 类似 quick sort 找出路径的中点 m ，计算出通过 m 满足条件的最大权重子路径。 这步会花 O(n lg n)的时间。 然後藉由 m 把路径分成两半，分别计算出只在该部份的最大权重子路径。 总时间会是 O(n lg^2 n)。 2. 类似 merge sort 找出路境的中点 m 。 计算第一个点到 m 的最大权重子路径， 以及把结尾在 m 的所有路径按照长度排序。 计算第 m + 1 个点到 n 的最大权重子路径， 以及把结尾在 m + 1 的所有路径按照长度排序。 藉由两半部的路径，找出通过 m 且满足条件的 最大权重子路径。 这步会花 O(n) 时间，总时间是 O(n lg n)。 很明显方法 1 在 计算通过 m 满足条件的最大权重子路径时有些重复计算。 所以方法 2 效率比较好。 然後把输入从路径改成树，思考最大权重子路径问题。 如果用 centroid decomposition，每次要计算出通过 centroid 且满足 条件的路径，需要花 O(n lg n)，这导致最後时间复杂度变成O(n lg^2 n)。 不过其实其中有一些是重复的计算。 这边我想不太到有没有什麽方法可以利用子树的计算来辅助， 主要是一个树可能会被从不同地方切开，一个子树可能会跟一堆其他树相接， 很难维护计算结果。 spine decomposition 不是用一个点把树切开，而是用一条 path 把 树切开，切开之後不是两半，而是一堆子树，每个子树与 path 的一个点 相接。 递回算出每个子树中最大权重子路径， 同时算出在每个子树中，终点在 path 上的所有路径按照且长度排序。 然後我们就可以在 path 上用类似方法 2 来 merge 了， 当然这边 merge 需要有技巧，要保证 merge 的两个子树差不多大， 而且 merge 两个子树只能花 O(n) 的时间。 不知道有长度下界的时候，能不能也做到O(n lg n)。 --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 129.170.195.149 ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1425496126.A.B1D.html ※ 编辑: FRAXIS (129.170.195.149), 03/05/2015 22:36:03