PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] 樹上路徑和為 k

看板Prob_Solve (計算數學 Problem Solving)作者FRAXIS (喔喔)時間9年前 (2015/03/05 03:08)推噓0(0推 0噓 1→)

留言1則, 1人參與討論串3/3 (看更多)

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