分治算法在樹的路徑問題中的應(yīng)用

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

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

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

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

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

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

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

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

9、uery On a Tree Ⅳ,,L,R,,,L,R,,,L,R,,設(shè)區(qū)間[L,R]的結(jié)點(diǎn)編號(hào)為P，Lc,Rc分別表示P的左右兩個(gè)兒子，區(qū)間[L,Mid]和[Mid+1,R]。我們可以得到如下轉(zhuǎn)移：,Query On a Tree Ⅳ,Opt,,Opt,,L,R,,Opt,,L,R,,設(shè)區(qū)間[L,R]的結(jié)點(diǎn)編號(hào)為P，Lc,Rc分別表示P的左右兩個(gè)兒子，區(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 Ⅳ,對(duì)于邊界情況[L,L],,MaxL = D(L)MaxR = D(L)Opt =,D2(i)表示第i個(gè)結(jié)點(diǎn)至子樹內(nèi)某個(gè)黑色結(jié)點(diǎn)的路徑中長(zhǎng)度的次大值。,問題只剩下如何維護(hù)D和D2的值,Query On a Tree Ⅳ,,,,…,,,該點(diǎn)的兒子到某個(gè)黑點(diǎn)路徑的最大長(zhǎng)度,鏈的頭結(jié)點(diǎn)到某個(gè)黑點(diǎn)路徑的最大

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

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

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

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

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

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

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

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

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

20、個(gè)數(shù)分別為S和N-S，不妨設(shè)S≥N-S。,,最優(yōu)方案指選取一條邊使得刪除這條邊后所分離出來的兩棵子樹的結(jié)點(diǎn)個(gè)數(shù)較大值最小。 設(shè)X為U的兒子中以X為根的子樹的結(jié)點(diǎn)個(gè)數(shù)最大的一個(gè)，我們考慮另一種方案(X,U)。 設(shè)除去邊(X,U)后以X為根的子樹結(jié)點(diǎn)個(gè)數(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