分治算法在樹的路徑問題中的應用

1、分治算法在樹的路徑問題中的應用,長沙市雅禮中學 漆子超,,樹的路徑問題,論文內(nèi)容,一、樹的分治算法,樹的分治的兩種常見形式：基于點的分治 基于邊的分治,二、樹的路徑剖分算法,三、樹的分治算法的進一步探討,如何改進基于邊的分治的時間復雜度,歸納為基于鏈的分治,一、樹的分治算法,樹的分治算法是分治思想在樹型結(jié)構上的體現(xiàn)。,兩種常見的形式,基于點的分治,兩種常見的形式,基于點的分治,1.選取一個點將無根樹轉(zhuǎn)為有根樹,2.遞歸處理每一顆以

2、根結(jié)點的兒子為根的子樹,,,,兩種常見的形式,基于邊的分治,兩種常見的形式,基于邊的分治,1.在樹中選取一條邊,2. 將原有的樹分成兩棵不相交的樹，遞歸處理。,,,,,效率分析,可以證明在基于點的分治中，如果每次都選取樹的重心，那么至多遞歸 O(LogN)次。,基于邊的分治最壞情況下遞歸次數(shù)為O(N)。,【例一】樹中點對統(tǒng)計,給定一棵N個結(jié)點的帶權樹。 定義dist(u，v)=u，v兩點間的路徑長度，路徑的長度定義為路徑上

3、所有邊的權和。 給定一個K，如果對于不同的兩個結(jié)點a，b，如果滿足dist(a，b)≤K，則稱(a，b)為合法點對。 求合法點對個數(shù)。,N≤10000,K≤109,一條路徑：,,,,,,,,,,,,,,1.過根節(jié)點,2.在一顆子樹內(nèi),?,樹中點對統(tǒng)計,記D(i) 表示節(jié)點i到根節(jié)點路徑的長度,Answer = 滿足 D(i)+D(j)≤K 的(i,j)個數(shù) i,j屬于不同的子樹,O(NlogN),樹中點

4、對統(tǒng)計,時間復雜度分析,,,,每層的時間復雜度不超過O(NlogN),最多遞歸O(logN)次,O(Nlog2N),二、路徑剖分算法,輕重邊路徑剖分,將樹中的邊分為兩類：輕邊和重邊。,,記Size(U)表示以U為根的子樹的結(jié)點個數(shù)。,令V為U的兒子中Size(V)最大的一個，那么我們稱邊(U，V)為重邊，其余邊為輕邊。,輕重邊路徑剖分,我們稱某條路徑為重路徑，當且僅當它全部由重邊組成。那么對于每個點到根的路徑上都不超過O(logN)條輕

5、邊和O(logN)條重路徑。,我們稱某條路徑為重路徑，當且僅當它全部由重邊組成。那么對于每個點到根的路徑上都不超過O(logN)條輕邊和O(logN)條重路徑。,路徑剖分算法常用來高效的維護點到根的路徑,Spoj的Qtree,Astar2008的黑白樹…,【例二】 Query On a Tree Ⅳ,給定一棵包含N個結(jié)點的樹，每個節(jié)點要么是黑色，要么是白色。要求模擬兩種操作： 1)改變某個結(jié)點的顏色。 2)詢

6、問最遠的兩個黑色結(jié)點之間的距離。,數(shù)據(jù)范圍： N≤100000,邊權絕對值不超過1000,此題出自2007年浙江省選,但此題中樹的邊權可能為負，無法使用括號序列。,另尋他法,路徑剖分算法,這道題的算法似乎與路徑剖分毫無關系，那么我們是否能用路徑剖分算法解決此題呢？,路徑剖分與樹的分治的聯(lián)系,一棵樹及其剖分,路徑剖分與樹的分治的聯(lián)系,路徑剖分每次刪除了一條鏈，所以路徑剖分算法可以看做是基于鏈的分治,按照點到根結(jié)點路徑上的輕

7、邊個數(shù)分層擺放。,遞歸樹！,Query On a Tree Ⅳ,將路徑剖分理解成基于鏈的分治后，我們可以用類似基于點的分治的方法將路徑分類。,1.與鏈有重合部分,2.與鏈沒有重合部分,,Query On a Tree Ⅳ,,,,,,,…,我們的目標就是要求出滿足與此鏈的重合部分在[1,N]的路徑的最大長度。,我們可以用線段樹解決這個問題。,Query On a Tree Ⅳ,記D(i)表示第i個結(jié)點至子樹內(nèi)某個黑色結(jié)點的路徑中長度的最大

8、值。Dist(i,j)表示鏈上的第i個點到第j個點的距離。,Query On a Tree Ⅳ,對于線段樹中的一個區(qū)間[L,R],我們需要記錄下面三個量：,,,= 與此鏈的重合部分在[L,R]的路徑的最大長度,,L,R,,L,R,Query On a Tree Ⅳ,,L,R,,,L,R,,,L,R,,,,設區(qū)間[L,R]的結(jié)點編號為P，Lc,Rc分別表示P的左右兩個兒子，區(qū)間[L,Mid]和[Mid+1,R]。我們可以得到如下轉(zhuǎn)移：,Q

9、uery On a Tree Ⅳ,,L,R,,,L,R,,,L,R,,設區(qū)間[L,R]的結(jié)點編號為P，Lc,Rc分別表示P的左右兩個兒子，區(qū)間[L,Mid]和[Mid+1,R]。我們可以得到如下轉(zhuǎn)移：,Query On a Tree Ⅳ,Opt,,Opt,,L,R,,Opt,,L,R,,設區(qū)間[L,R]的結(jié)點編號為P，Lc,Rc分別表示P的左右兩個兒子，區(qū)間[L,Mid]和[Mid+1,R]。我們可以得到如下轉(zhuǎn)移：,Query On a

10、 Tree Ⅳ,注意到Dist(i,j) = Dist(1,j) – Dist(1,i),O(1),Query On a Tree Ⅳ,對于邊界情況[L,L],,MaxL = D(L)MaxR = D(L)Opt =,D2(i)表示第i個結(jié)點至子樹內(nèi)某個黑色結(jié)點的路徑中長度的次大值。,問題只剩下如何維護D和D2的值,Query On a Tree Ⅳ,,,,…,,,該點的兒子到某個黑點路徑的最大長度,鏈的頭結(jié)點到某個黑點路徑的最大

11、長度,！,這正是我們前面已經(jīng)維護了的量MaxL,一個點向下至某個黑色結(jié)點的路徑,Query On a Tree Ⅳ,我們可以使用堆來維護一個點向下至某個黑色結(jié)點的路徑長度集合,O(1),時間復雜度分析,詢問操作： 我們使用堆來存貯每條鏈的最優(yōu)結(jié)果,修改操作： 修改一個點最多影響O(logN)條鏈，對于每條鏈我們需要修改堆和線段樹，O(logN),O(1),O(log2N),路徑剖分,AC,三、樹的分治算法的進

12、一步探討,基于點的分治,刪除一個點后樹的個數(shù)太多，加大了設計高效算法的難度,基于邊的分治,,刪除一條邊后僅有兩棵樹,最壞的時間復雜度限制了該算法的應用,改進!,如何改進基于邊的分治的時間復雜度,改變選擇邊的方法？,X,改變樹的結(jié)構！,無論選擇哪條邊，結(jié)果都是一樣的,如何改進基于邊的分治的時間復雜度,回想上題，題目所關注的對象是兩個黑點之間的距離，這就提醒我們可以在不影響樹中黑色結(jié)點之間的距離的前提下加入白色結(jié)點,,,如何改進基于邊的分治

13、的時間復雜度,通過對每個結(jié)點到其兒子的路徑中加入了白色結(jié)點，使之成為了類似線段樹的結(jié)構。,葉節(jié)點為N的線段樹共有2N個結(jié)點，所以含有N個結(jié)點的樹轉(zhuǎn)化后所得的新樹最多包含2N個結(jié)點。,每個點的度至多為3,如何改進基于邊的分治的時間復雜度,定理： 如果一棵包含N個結(jié)點的樹中每個點的度均不大于D，那么存在一條邊，使得分出的兩棵子樹的結(jié)點個數(shù)在[N/(D+1),N*D/(D+1)]。,改進后的算法最壞情況下遞歸深度為

14、 O(LogN),使用基于邊的分治解決上題,一條路徑：,1.過中心邊,2.在一顆子樹內(nèi),,,,,1.過中心邊,使用基于邊的分治解決上題,,,,記錄兩個根結(jié)點到其子樹內(nèi)某個黑色結(jié)點的路徑的最大長度,最優(yōu)路徑,修改O(logN)詢問O(1),時間復雜度分析,詢問操作： 對每顆樹都記錄其兩個子樹的最優(yōu)值,修改操作： 一個點最多屬于O(lo

15、gN)棵樹，對于每棵樹我們需要修改堆，O(logN),O(1),O(log2N),我們達到了與使用路徑剖分同階的時間復雜度。,算法更加簡單,總結(jié),1.算法的常數(shù)： 基于鏈的分治 < 基于點的分治 < 基于邊的分治,2.基于鏈的分治可以用來維護路徑上的點(邊)。如果維護的對象是路徑的長度，基于點(邊)的分治算法的能力更強。,這幾個算法各有所長，需要我們根據(jù)具體情況，靈活運用，以最佳的方式解決題目。,3.與基于點的分治比較

16、，基于邊的分治在設計高效算法的思考難度上明顯小于前者。,謝謝大家,算法的常數(shù),1.在路徑剖分算法中，鏈的長度和鏈的個數(shù)是相互制約的，因此路徑剖分算法在實際運行中是很快的。,2.為了改進基于邊的分治的最壞復雜度，我們將一個結(jié)點個數(shù)為N的樹改造成了一個結(jié)點個數(shù)為2N的新樹，自然增加了常數(shù)。,算法的常數(shù),測試環(huán)境：Intel® Core?2 Duo T7250 2.00GHz,1GB編譯器：Visual C++ 2008 , R

17、elease 模式,算法的常數(shù),測試環(huán)境：Intel® Core?2 Duo T7250 2.00GHz,1GB編譯器：Visual C++ 2008 , Release 模式 Free Pascal 2.1.4,樹的重心,我們選取一個點，要求將其刪去后，結(jié)點最多的樹的結(jié)點個數(shù)最小，這個點被稱作”樹的重心” 。,定理：存在一個點使得分出的子樹的結(jié)點個數(shù)均不大于N/2,假設U是樹的重心，記Siz

18、e(X)表示以X為根的子樹的結(jié)點個數(shù)。記V為U的兒子中Size值最大的點。,證明：,,定理：存在一個點使得分出的子樹的結(jié)點個數(shù)均不大于N/2,證明：,假設Size(V)>N/2，那么我們考慮V作為根結(jié)點的情況，記Size’(X)表示此時以X為根的子樹的結(jié)點個數(shù)。,,定理：存在一個點使得分出的子樹的結(jié)點個數(shù)均不大于N/2,證明：,如圖。 對于A部分，顯然Size’(Ti)<Size(V) 對于B部分，Size’

19、(U) = N-Size(V)<Size(V) 這與樹的重心定義矛盾。 定理得證。,,定理： 如果一棵包含N個結(jié)點的樹中每個點的度均不大于D，那么存在一條邊，使得分出的兩棵子樹的結(jié)點個數(shù)在[N/(D+1),N*D/(D+1)]。,證明： 不妨令D為所有點的度的最大值。 當D=1時，命題顯然。 當D>1時，我們設最優(yōu)方案為邊(U,V)，且以U,V為根的兩棵子樹的結(jié)點

20、個數(shù)分別為S和N-S，不妨設S≥N-S。,,最優(yōu)方案指選取一條邊使得刪除這條邊后所分離出來的兩棵子樹的結(jié)點個數(shù)較大值最小。 設X為U的兒子中以X為根的子樹的結(jié)點個數(shù)最大的一個，我們考慮另一種方案(X,U)。 設除去邊(X,U)后以X為根的子樹結(jié)點個數(shù)為P，顯然P≥(S-1)/(D-1)，由于P<S且邊(U,V)是最優(yōu)方案，所以N-P≥S，與P≥(S-1)/(D-1)聯(lián)立可得S≤((D-1)N+1)/D，又N≥D