算法合集之《動(dòng)態(tài)樹(shù)問(wèn)題及其應(yīng)用》.pptVIP

Dynamic Trees Problem, and its applications,湖南省長(zhǎng)郡中學(xué) 袁昕顥 xinhaoyuanatgmaildotcom,Overview,動(dòng)態(tài)樹(shù)問(wèn)題 給出動(dòng)態(tài)樹(shù)問(wèn)題的基本形式. 解決動(dòng)態(tài)樹(shù)問(wèn)題 提出新的Rake & Compress方法. 動(dòng)態(tài)樹(shù)問(wèn)題的應(yīng)用 用最大流算法來(lái)說(shuō)明動(dòng)態(tài)樹(shù)問(wèn)題的應(yīng)用.,Part I. Dynamic Trees Problem,Dynamic Trees Problem,動(dòng)態(tài)樹(shù)問(wèn)題(Dynamic Trees Problem)是圖論中一類(lèi)非常重要的經(jīng)典問(wèn)題. 許多圖論算法, 尤其是在線(xiàn)動(dòng)態(tài)算法都將其作為瓶頸問(wèn)題. 研究和解決該問(wèn)題具有很高的理論價(jià)值和實(shí)際價(jià)值. 什么是動(dòng)態(tài)樹(shù)問(wèn)題呢?,Dynamic Trees Problem,維護(hù)一個(gè)包含N個(gè)點(diǎn)的森林, 并且支持形態(tài)和權(quán)值信息的操作. 形態(tài)信息,Dynamic Trees Problem,維護(hù)一個(gè)包含N個(gè)點(diǎn)的森林, 并且支持形態(tài)和權(quán)值信息的操作. 形態(tài)信息 Link(u,v) 添加邊(u,v),Dynamic Trees Problem,維護(hù)一個(gè)包含N個(gè)點(diǎn)的森林, 并且支持形態(tài)和權(quán)值信息的操作. 形態(tài)信息 Link(u,v) 添加邊(u,v) Cut(u,v) 刪除邊(u,v),Dynamic Trees Problem,維護(hù)一個(gè)包含N個(gè)點(diǎn)的森林, 并且支持形態(tài)和權(quán)值信息的操作. 形態(tài)信息 Link(u,v) 添加邊(u,v) Cut(u,v) 刪除邊(u,v) Find(u) 找到u所在的樹(shù).,Dynamic Trees Problem,維護(hù)一個(gè)包含N個(gè)點(diǎn)的森林, 并且支持形態(tài)和權(quán)值信息的操作. 權(quán)值信息,Dynamic Trees Problem,維護(hù)一個(gè)包含N個(gè)點(diǎn)的森林, 并且支持形態(tài)和權(quán)值信息的操作. 權(quán)值信息 路徑操作: 對(duì)一條簡(jiǎn)單路徑上的所有對(duì)象進(jìn)行操作,Dynamic Trees Problem,維護(hù)一個(gè)包含N個(gè)點(diǎn)的森林, 并且支持形態(tài)和權(quán)值信息的操作. 權(quán)值信息 路徑操作: 對(duì)一條簡(jiǎn)單路徑上的所有對(duì)象進(jìn)行操作 樹(shù)操作: 對(duì)一棵樹(shù)內(nèi)的所有對(duì)象進(jìn)行操作,現(xiàn)有結(jié)果,理論補(bǔ)充,對(duì)于一個(gè)完整的動(dòng)態(tài)樹(shù)問(wèn)題, 目前公認(rèn)的下界是O(log2N) per operation, 并已經(jīng)被上述方法達(dá)到. 但是由于巨大的常數(shù)因子, 動(dòng)態(tài)樹(shù)在實(shí)踐中并沒(méi)有發(fā)揮應(yīng)有的作用. 動(dòng)態(tài)樹(shù)問(wèn)題仍然沒(méi)有完美解決, 并且仍然處在熱烈討論中.,Part II. Solving Dynamic Trees Problem,New Idea,在這里, 我向大家介紹一種新的解決動(dòng)態(tài)樹(shù)問(wèn)題的思路. 這種思路簡(jiǎn)單, 而且, 可以得到效率非常高的具體實(shí)現(xiàn).,I. 樹(shù), 與其平面刻畫(huà).,一棵樹(shù)的平面刻畫(huà), 直觀(guān)地說(shuō)就是將一棵樹(shù)的點(diǎn)和邊畫(huà)在平面上. 邊與邊僅在頂點(diǎn)處相交.,I. 樹(shù), 與其平面刻畫(huà).,一棵樹(shù)的平面刻畫(huà), 直觀(guān)地說(shuō)就是將一棵樹(shù)的點(diǎn)和邊畫(huà)在平面上. 邊與邊僅在頂點(diǎn)處相交. 確定一棵樹(shù)的平面刻畫(huà), 等價(jià)于確定這棵樹(shù)的Euler Tour.,II. 等價(jià)映射,事實(shí)上, 所有解決動(dòng)態(tài)樹(shù)問(wèn)題的方法, 歸根結(jié)底都使用等價(jià)映射的基本思想. 即, 將任意形態(tài)的樹(shù)(原樹(shù))映射到度限制, 深度平均的新樹(shù)(像樹(shù)).,III. Rake & Compress,這里介紹一種Rake & Compress5,6方法. 即將原樹(shù)映射到一棵Rake & Compress Trees (Abbr. R&C Trees). R&C Trees由Rake節(jié)點(diǎn)和Compress節(jié)點(diǎn)組成.,1. Rake Nodes,Rake節(jié)點(diǎn)i是原樹(shù)中以某節(jié)點(diǎn)為根的有根子樹(shù)的映射.,Root,1. Rake Nodes,Rake節(jié)點(diǎn)i是原樹(shù)中以某節(jié)點(diǎn)為根的有根子樹(shù)的映射. 特別地, 如果該節(jié)點(diǎn)僅包含根本身, 那么該Rake節(jié)點(diǎn)沒(méi)有后繼(葉子節(jié)點(diǎn)). 否則令Next(i)表示i所代表的除了根以外的其它點(diǎn)組成的集合.,Root,2. Compress Nodes,Compress節(jié)點(diǎn)j, 是原樹(shù)中以某條路徑為根的有根子樹(shù)的映射.,s,e,2. Compress Nodes,Compress節(jié)點(diǎn)j, 是原樹(shù)中以某條路徑為根的有根子樹(shù)的映射. 特別地, 如果路徑長(zhǎng)度為1. 那么該Compress節(jié)點(diǎn)沒(méi)有后繼. 否則令Next(j)表示j代表的路徑上的非端點(diǎn)集合.,s,e,3. R&C Trees,對(duì)于一個(gè)非葉子Rake/Compress節(jié)點(diǎn)i, Next(i)非空. 對(duì)于每個(gè)Next(i)中的元素j. 我們采用如下方法劃分節(jié)點(diǎn)i:,1 Rake節(jié)點(diǎn)的劃分,令r表示i的根.,r,j,1 Rake節(jié)點(diǎn)的劃分,令r表示i的根. 將路徑j(luò)r作為新的Compress節(jié)點(diǎn).,r,j,1 Rake節(jié)點(diǎn)的劃分,令r表示i的根. 將路徑j(luò)r作為新的Compress節(jié)點(diǎn). 將j和j的子孫作為新的Rake節(jié)點(diǎn).,r,j,1 Rake節(jié)點(diǎn)的劃分,令r表示i的根. 將路徑j(luò)r作為新的Compress節(jié)點(diǎn). 將j和j的子孫作為新的Rake節(jié)點(diǎn). i中路徑j(luò)r的左手方向和右手方向各為一個(gè)新的Rake節(jié)點(diǎn).,r,j,2 Compress節(jié)點(diǎn)的劃分,令s,e分別表示i中路徑的頭和尾.,s,e,j,2 Compress節(jié)點(diǎn)的劃分,令s,e分別表示i中路徑的頭和尾. sj,je分別成為新的Compress節(jié)點(diǎn),s,e,j,2 Compress節(jié)點(diǎn)的劃分,令s,e分別表示i中路徑的頭和尾. sj,je分別成為新的Compress節(jié)點(diǎn) j的其他子孫被劃分成兩部分, 分別作為新的Rake節(jié)點(diǎn).,s,e,j,R&C Trees,約定, 一個(gè)有根樹(shù)對(duì)應(yīng)R&C Trees就是整個(gè)樹(shù)的Rake Node. 這樣的分解方式本身就保證度的限制(一個(gè)節(jié)點(diǎn)最多被剖分出4個(gè)子節(jié)點(diǎn)) 我們以右圖為例，展示一棵原樹(shù)如何被映射到像樹(shù)。,Level 1,選取I作為第1層剖分點(diǎn)，原Rake節(jié)點(diǎn)被剖分成4個(gè)部分，4個(gè)部分分別剖分。,Level 2,選取B,C,D,L作為第2層剖分點(diǎn)。,Level 3,選取F,E,G,H,K,J作為第3層剖分點(diǎn)。,Final,這樣，我們就構(gòu)建出了整個(gè)樹(shù)的R&C Trees。,Randomized,決定R&C Trees深度的關(guān)鍵因素在于選擇Next(i)中元素的方法. 一個(gè)比較好的方法是, 隨機(jī)選擇! 如果等概率的選擇Next(i)中的元素, 可以證明這樣的深度下界是(ln2N). 問(wèn)題并沒(méi)有完全解決. 必須采取更為合理的隨機(jī)策略.,Randomized,對(duì)于Rake節(jié)點(diǎn), 仍然采取等概率的方法選擇. 對(duì)于Compress節(jié)點(diǎn)i, j表示Next(i)中的元素, 令Weight(j)表示j剩余的子孫個(gè)數(shù)(包括j). 現(xiàn)在以Weight(j)作為加權(quán), 令S表示所有Weight(k)的和, 則j有Weight(j)/S的概率被選擇.,Randomized : Master Theorem,可以證明, 通過(guò)這樣合理的改造, 一個(gè)N的點(diǎn)的樹(shù)可以被映射到一個(gè)期望深度為O(lnN)的R&C Trees. 基于這種思想, RP-Trees被提出. 事實(shí)上, 這就是Treap7通過(guò)R&C思想在任意樹(shù)的拓展. 通過(guò)這種思想, 我們可以得到均攤, 甚至是嚴(yán)格深度O(lnN)的算法.,小結(jié),相比較于Path Decomposing和Divide & Conquer, Rake & Compress具有思想簡(jiǎn)單, 常數(shù)小, 實(shí)現(xiàn)復(fù)雜度低等特點(diǎn). R&C思想最大的特點(diǎn)是, 利用這種思想可以很方便地將各種平衡二叉樹(shù)技巧拓展到任意樹(shù)形態(tài)上去. 為Dynamic Trees Problem 注入了新的血液.,Part III. Applications,Applications ,網(wǎng)絡(luò)優(yōu)化 最大流4 最小費(fèi)用流 動(dòng)態(tài)算法 動(dòng)態(tài)連通性3,8 動(dòng)態(tài)最小生成森林3 ,最大流問(wèn)題,最大流問(wèn)題是非常經(jīng)典的圖論問(wèn)題. 經(jīng)典的解決算法有最短增廣路, 預(yù)流推進(jìn). 通過(guò)改造最短增廣路算法并應(yīng)用動(dòng)態(tài)樹(shù), 可以得到O(NMlnN)的算法. N為點(diǎn)數(shù), M為邊數(shù). 經(jīng)典的最短增廣路算法是通過(guò)BFS, 每次在殘余網(wǎng)絡(luò)中找到一條最短S-T增廣路并進(jìn)行增廣.,Residual network,Residual network,找到最短增廣路 SC E T 增廣量為3,Residual network,Residual network,找到最短增廣路 SA E T 增廣量為8,Residual network,最大流問(wèn)題,引理: 只需要O(NM)次增廣. 證明: 考察當(dāng)前最短路的必要邊集A 所有ST的最短路全部由A中元素組成 |A|M 每次都找到最短增廣路, 增廣后A中元素必有一條邊被刪除(殘余量為0).,最大流問(wèn)題,在ST最短路長(zhǎng)度被提高之前不可能有邊從A外加入到A內(nèi). O(M)次增廣后ST增廣路長(zhǎng)度必被提高. 因此最多執(zhí)行O(NM)次增廣. 綜上所述, 引理得證.,最大流問(wèn)題,原始算法的時(shí)間復(fù)雜度為O(NM2). 令D(x)表示x到T的最短增廣路下界. 對(duì)于所有殘余量0的邊uv, 滿(mǎn)足D(u)D(v)+1. 如果D(u)=D(v)+1, 則稱(chēng)uv為有效邊. 引理: 全部由有效邊組成的到T的路徑一定是最短路徑!,最大流問(wèn)題,每次在殘余網(wǎng)絡(luò)中沿著讓D(x)遞減的有效邊前進(jìn). 并不斷修正(抬高)D(x). 可以證明, 該優(yōu)化方法將尋找最短增廣路的時(shí)間降為均攤O(N), 所以需要的總時(shí)間降為O(N2M). 那么, 能不能再次改進(jìn)呢?,最大流問(wèn)題,一個(gè)想法是, 維護(hù)有效邊子集的生成森林. 如果S, T不在同一棵樹(shù)內(nèi). 令R為S所在樹(shù)內(nèi)D值最小的點(diǎn)(最低點(diǎn)), 如果存在有效邊RR, 則執(zhí)行Link(R,R). 如果此時(shí)R沒(méi)有連出的有效邊, 顯然D(R)是可以改進(jìn)的. 即這個(gè)下界是松的, 此時(shí)我們抬高D(R). 并更新有效邊集. 當(dāng)S和T都在同一棵樹(shù)內(nèi)時(shí)(即最低點(diǎn)為T(mén)), 對(duì)樹(shù)中的S-T路徑進(jìn)行增廣. 每次所增廣的路都是最短增廣路.,Residual network,黑色邊為有效邊,Residual network,紅色邊為生成森林邊,Residual network,找到一條由當(dāng)前最低點(diǎn)A連出的有效邊AE 執(zhí)行Link(A,E),Residual network,找到最短增廣路 SAET 增廣量為8,Residual network,增廣后AE不再有效 Cut(A,E),Residual network,嘗試找到從最低點(diǎn)A連出的邊，失敗 抬高D(A)并更新有效邊,Residual network,找到一條由當(dāng)前最低點(diǎn)S連出的有效邊SC 執(zhí)行Link(S,C),Residual network,找到一條由當(dāng)前最低點(diǎn)C連出的有效邊CE 執(zhí)行Link(C,E),Residual network,找到最短增廣路 SCET 增廣量為3,Residual network,最大流問(wèn)題,由于流程和最短增廣路一樣, 故正確性顯然. 現(xiàn)在考察其時(shí)間復(fù)雜度.,最大流問(wèn)題,前面已經(jīng)說(shuō)過(guò), 最多執(zhí)行O(NM)次增廣, 所以在增廣上的總時(shí)間為O(NMlnN). 因?yàn)?D(x)N, 所以最多執(zhí)行O(NM)次Cut操作. 因此花費(fèi)在Cut上的總時(shí)間為O(NMlnN). 又因?yàn)樵谝粋€(gè)點(diǎn)的D值被抬高之前, 每個(gè)點(diǎn)均攤被Link過(guò)1次. 綜上所述, 總的時(shí)間復(fù)雜度為O(NMlnN),時(shí)間復(fù)雜度,時(shí)間復(fù)雜度,時(shí)間復(fù)雜度,小結(jié),使用動(dòng)態(tài)樹(shù)問(wèn)題來(lái)優(yōu)化算法的關(guān)鍵是解決瓶頸問(wèn)題. 在本例中, 我們將復(fù)雜度攤平到了每一種操作中. 使得總的時(shí)間復(fù)雜度獲得了質(zhì)的飛躍. 其實(shí), 不僅僅是最大流算法, 網(wǎng)絡(luò)優(yōu)化的很多算法都可以使用動(dòng)態(tài)樹(shù)來(lái)優(yōu)化, 并得到很好的理論復(fù)雜度.,總結(jié),研究動(dòng)態(tài)樹(shù)問(wèn)題是非常有價(jià)值的, 研究它可以加深對(duì)圖論的理解. 其解決方法使用的技巧亦非常具有啟發(fā)性. 更何況其問(wèn)題本身又是那么美妙! 對(duì)于一個(gè)復(fù)雜的經(jīng)典問(wèn)題, 我們不應(yīng)僅僅滿(mǎn)足于“知道” 或者“學(xué)會(huì)”, 更需要融會(huì)貫通. 這對(duì)我們無(wú)論是日常學(xué)習(xí)或者競(jìng)賽活動(dòng)都是非常有好處的.,References,1 Daniel D. Sleator, Robert Endre Tarjan, A data structure for dynamic trees, Journal of Computer and System Sciences, v.26 n.3, p.362-391, June 1983. 2 Daniel Dominic Sleator , Robert Endre Tarjan, Self-adjusting binary search trees, Journal of the ACM (JACM), v.32 n.3, p.652-686, July 1985 3 S. Alstrup, J. Holm, K. de Lichtenberg, and M. Thorup. Minimizing diameters of dynamic trees. In Proceedings of the 24th International Colloquium on Automata, Languages and Programming, pages 270-280, 1997. 4 Ahujia, R. K. Dynamic Trees Implementations. Network Flows: Theory, Algorithms, and Applications, p.265-273. 5 R. Tarjan and R. Werneck