《淺析樹(shù)的劃分問(wèn)題》

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

最優(yōu)劃分

上方

“序”的概念

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

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

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

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

問(wèn)題轉(zhuǎn)化

二分法算法2

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