※ 引述《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/m.aspx?n=bbs/Prob_Solve/M.1425496126.A.B1D.html ※ 編輯: FRAXIS (129.170.195.149), 03/05/2015 22:36:03