《淺析樹的劃分問題》

淺析樹的劃分問題整理ppt概要 樹的劃分問題：將給定的一棵樹劃分為若干棵子樹，使其能夠滿足一定的條件或是使得某個特定的函數(shù)達到最值。樹的最大－最小劃分問題。整理ppt問題的提出草莓（NOI2003Day2-2test6～test9）題目大意：給出一片草莓中每個草莓的重量以及它們的連接情況。令sum(i)表示第i塊草莓田中所有草莓重量的和(1≤i≤k),

x=min{sum(i)|1≤i≤k}。你的任務(wù)就是要把一塊草莓田分割成k塊，且分割方案需要滿足如下的條件：每一塊中的草莓必然是直接或者間接的和其他草莓相連接的；這種分割方案所對應(yīng)的x盡可能的大。最后輸出你的分割方案和結(jié)果。整理ppt問題的提出這是一道提交答案式的題目，其中test6～test9所給的圖是一棵樹，若不考慮具體的數(shù)據(jù)情況，我們可以將原問題抽象成如下問題：

給定一棵樹以及樹中每個頂點的一個非負權(quán)值，將樹劃分為k棵子樹，定義：sum(i)表示第i棵子樹中所有頂點權(quán)值的和，x=min{sum(i)|1≤i≤k}，請求出x的最大值并輸出一種劃分方案。

我們把它稱作樹的最大－最小劃分問題。整理ppt算法1：問題轉(zhuǎn)化考慮新問題：對于一個確定的下界，最多可將樹劃分為多少棵子樹，使得每棵子樹的權(quán)值和都不小于此下界？新問題＋二分法原問題整理ppt解決新問題新問題的解決只需要一個以貪心思想為基礎(chǔ)的掃描算法。

393531264下界：1035124173106整理ppt解決原問題時間復(fù)雜度：O(N)已是理論下界通過二分法來找到最大的下界x，使得劃分的最大子樹數(shù)目不小于k，x即為原問題的解。整理ppt小結(jié)解決問題的途徑：問題轉(zhuǎn)化實現(xiàn)簡單，運行效果好

運行時間依賴于節(jié)點的權(quán)值范圍若節(jié)點的權(quán)值范圍很大或者權(quán)值是小數(shù)甚至無理數(shù)……

時間復(fù)雜度不依賴于節(jié)點權(quán)值范圍的算法？Perfect！?整理ppt新思路：割一條邊所連接的兩個頂點分屬不同的子樹，則稱在這條邊上有一個“割”。每個割對應(yīng)一棵子樹+根節(jié)點所在子樹劃分k棵子樹

將k-1個割分配到k-1個不同的邊上整理ppt新思路：移動一次移動被定義為將一個割從一條邊移到一條與它相鄰的邊上，并且保證新的邊一定是在原來那條邊的下一層。

新算法:初始狀態(tài)+移動規(guī)則關(guān)鍵點整理ppt初始狀態(tài)最簡單的方法：

·任選一個度為1的頂點為根·將所有割都放在與根相連的唯一的邊上可以由初始狀態(tài)到達任何一個目標狀態(tài)關(guān)鍵：移動規(guī)則的制定整理ppt移動規(guī)則依據(jù)的還是一種貪心的思想：

1.計算出當前狀態(tài)下子樹權(quán)值和的最小值Wmin2.考慮所有可能的移動，找出能使移動后的割所對應(yīng)的子樹權(quán)值和Wnow最大的那種移動3.如果Wnow≥Wmin，那么進行這步移動，并轉(zhuǎn)到步驟14.算法結(jié)束，Wmin

即為所求的最大的最小值，當前劃分即為一種最優(yōu)劃分

證明？整理ppt例子79139128當前劃分一種最優(yōu)劃分整理ppt“上方”當前劃分總是在某個最優(yōu)劃分的“上方”“上方”的定義

劃分A在劃分A’的上方，也就是存在一種A的割和A’的割的一一對應(yīng)，使得每個A的割都在它所對應(yīng)的A’的割的上方。更加實用的性質(zhì)

？整理ppt定義：部分子樹若一棵樹T的子樹T’包含了頂點v連同v的某一個兒子以及這個兒子的所有后繼，則稱T’是T在頂點v處的一棵部分子樹。與v相連的唯一一條邊被稱為T’的初始邊。v初始邊整理ppt重要性質(zhì)劃分A在劃分A’上方AA’#(A)≤#(A’)整理ppt證明算法(1)在初始狀態(tài)時的劃分A是在任何一個最優(yōu)劃分Q的上方的。(2)若存在一個最優(yōu)劃分Q使得當前的劃分A是在Q的上方，且A和Q不相等，則算法一定不會終止。(3)設(shè)A在Q的上方且A不等于Q，在算法進行一步后A變?yōu)锳’，我們一定還能找到一個最優(yōu)劃分Q’使得A’在Q’上方。(4)算法會在有限步內(nèi)終止，算法終止時的劃分一定是一個最優(yōu)劃分。整理ppt一些說明字母A表示由算法進行而得到的劃分。字母Q表示一個最優(yōu)劃分，即使得最小子樹最大的劃分。用Wmin(A)表示在劃分A下的最小子樹的權(quán)值和對于任意劃分A，Wmin(A)≤Wmin(Q)整理ppt證明算法(2)(2)若存在一個最優(yōu)劃分Q使得當前的劃分A是在Q的上方，且A和Q不相等，則算法一定不會終止。當前劃分A最優(yōu)劃分Qcsc’c’≥Wmin(Q)≥Wmin(Q)≥Wmin(A)整理ppt證明算法(3)(3)設(shè)A在Q的上方且A不等于Q，在算法進行一步后A變?yōu)锳’，我們一定還能找到一個最優(yōu)劃分Q’使得A’在Q’上方。ccsse1e2v≥Wmin(Q)當前劃分A最優(yōu)劃分Q情況1：對于在頂點v處的每一棵部分子樹T’，都有#(A)=#(Q)。

整理ppt證明算法(3)情況2：存在在頂點v處的某棵子樹T’，使得#(A)<#(Q)。cce1e2vss≥Wmin(Q)≥Wmin(Q)≥Wmin(Q)e3當前劃分A最優(yōu)劃分Q呼，終于證完了……整理ppt小結(jié)新思想，新方向：割，移動貫穿整個證明過程的思想：上方當前劃分

最優(yōu)劃分

上方

“序”的概念

整理ppt算法的擴展權(quán)函數(shù)的擴展子樹中所有節(jié)點的權(quán)值之和子樹中節(jié)點權(quán)值最大值？子樹半徑？（樹的P中心問題）

……？權(quán)函數(shù)的必要條件：

若T’是T的任意一棵子樹，則W(T)≥W(T’)，其中W(T)表示樹T的權(quán)函數(shù)

整理ppt總結(jié)兩個算法，它們通過不同的方式思考問題，從而得到了不同的解法算法1

問題轉(zhuǎn)化

二分法算法2

割，移動“上方”的概念整理ppt總結(jié)從不同的角度看問題深入思考問題深刻了