第10章競(jìng)賽樹

1、第10章 競(jìng)賽樹學(xué)習(xí)內(nèi)容m競(jìng)賽樹q完全二叉樹，高效替換最大（小）元q按指定的方式斷開連接m勝者樹、敗者樹m應(yīng)用：裝箱問題（bin packing）10.1 引言mn個(gè)選手進(jìn)行乒乓球淘汰賽m最終剩下一名勝者競(jìng)賽優(yōu)勝者勝者樹m將比賽用樹的結(jié)構(gòu)來描述m外部節(jié)點(diǎn)選手，內(nèi)部節(jié)點(diǎn)比賽結(jié)果mwinner tree：內(nèi)部節(jié)點(diǎn)記錄勝者m競(jìng)賽樹選擇樹（selection tree）定義m定義勝者樹：對(duì)于n 名選手，勝者樹是一棵含n 個(gè)外部節(jié)點(diǎn)，n1個(gè)內(nèi)部節(jié)點(diǎn)的完全二叉樹，每個(gè)內(nèi)部節(jié)點(diǎn)記錄了相應(yīng)賽局的勝者勝者樹例勝者樹的修改m選手d的得分發(fā)生改變q他與c的比賽結(jié)果可能改變?nèi)舾淖?，與a的比賽結(jié)果也可能改變q需修改d根

2、路徑上的節(jié)點(diǎn)，遇到比賽結(jié)果未變的節(jié)點(diǎn)即停止qO(logn)mn個(gè)選手n-1場(chǎng)比賽初始化Q(n)例10-1排序m最小勝者樹， Q(nlogn)qn個(gè)元素n名選手，初始化勝者樹q元素的值較小勝q最后的勝者最小值元素q將該選手（元素）的值改為最大值(如)必?cái)?，重?gòu)該贏者樹最終勝者為次大元素例10-1排序q重復(fù)，可以完成n個(gè)元素的排序q初始化時(shí)耗為Q(n)q每次改變勝者的值并重構(gòu)勝者樹的Q(logn)，共n-1次，排序總時(shí)間為(nlogn)例10-2外部排序m外部排序q數(shù)據(jù)集過大，無法全部放在內(nèi)存中q一部分、一部分地放在內(nèi)存中處理、排序q產(chǎn)生部分排序結(jié)果runq將若干run合并在一起得到最終的run例

3、10-2外部排序m16000個(gè)數(shù)據(jù)q內(nèi)存中一次可排序1000個(gè)數(shù)據(jù)（一個(gè)run）q生成16個(gè)runq將這16個(gè)run 4個(gè)4個(gè)地合并，5個(gè)步驟后就合并為單一的run合并run的方法m合并k個(gè)runq從k個(gè)run的前面不斷移出元素（各個(gè)run中最小值），選擇其中最小的（所有未處理數(shù)據(jù)中最小的），放入輸出run中q當(dāng)所有數(shù)據(jù)都移入到輸出run中，則結(jié)束q最少需要多少內(nèi)存？實(shí)際合并run的例子m上例q16000個(gè)數(shù)據(jù)，每個(gè)run 1000個(gè)數(shù)據(jù)q合并4個(gè)run，內(nèi)存分為5個(gè)緩沖區(qū)，4個(gè)輸入，1個(gè)輸出，均為200個(gè)數(shù)據(jù)大小q不斷從輸入緩沖區(qū)讀取數(shù)據(jù)，放入輸出緩沖區(qū)輸出緩沖區(qū)已滿寫入磁盤，繼續(xù)合并某個(gè)輸

4、入緩沖區(qū)空，讀取輸入run，繼續(xù)合并q4000個(gè)數(shù)據(jù)都寫入輸出run，合并結(jié)束利用勝者樹生成runmn個(gè)數(shù)的序列，逐個(gè)掃描，構(gòu)造run1.p個(gè)選手的勝者樹，選手輸入元素2.選手得分 值（元素值） run號(hào)（前p個(gè)選手均為1）3.勝負(fù)判定 先比較run號(hào)，較小者勝 run號(hào)相同，值小者勝利用勝者樹生成run4.重復(fù)以下步驟1) 將最終勝者W放入run中，哪個(gè)run？它的run號(hào)所指定的那個(gè)2) 在輸入序列中選取下一元素N取代W若其值大于等于W，設(shè)置相同run號(hào)否則，run號(hào)設(shè)為W的run號(hào)加1重構(gòu)勝者樹qrun的平均長度為2p為什么？利用勝者樹進(jìn)行k路合并m每產(chǎn)生一個(gè)輸出run元素k個(gè)輸入run

5、元素尋找最小值：O(kn)m利用勝者樹求最小值：Q(k+nlogk)10.2 勝者樹抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型WinnerTree實(shí)例完全二叉樹，每個(gè)節(jié)點(diǎn)代表相應(yīng)比賽的贏者，外部節(jié)點(diǎn)代表選手操作Create()：創(chuàng)建一個(gè)空的贏者樹Initialize(a, n)：對(duì)有n個(gè)選手a1:n的贏者樹進(jìn)行初始化Winner()：返回比賽的贏者Replay(i)：選手i變化時(shí)，重組贏者樹10.3 勝者樹的實(shí)現(xiàn)10.3.1 定義m特殊完全二叉樹公式化描述q選手e1:nq勝者樹內(nèi)部節(jié)點(diǎn)t1:n-1ti內(nèi)容：勝者數(shù)組e的索引樹和數(shù)組元素的對(duì)應(yīng)關(guān)系關(guān)鍵：尋找父節(jié)點(diǎn)m外部節(jié)點(diǎn)ei，確定其父節(jié)點(diǎn)tpq內(nèi)部節(jié)點(diǎn)最底層最左

6、節(jié)點(diǎn)編號(hào)2s，s=q最底層內(nèi)部節(jié)點(diǎn)數(shù)目n-2sq最底層外部節(jié)點(diǎn)數(shù)目LowExt=(n-2s)*2) 1(log2n關(guān)鍵：尋找父節(jié)點(diǎn)qi：完全二叉樹統(tǒng)一編號(hào)映射為父節(jié)點(diǎn)p編號(hào)q最終公式為LowExtinLowExtiLowExtiips),1(, 2/ )21(110.3.2 公式化描述的實(shí)現(xiàn)templateclass WinnerTree public: WinnerTree(int TreeSize = 10); WinnerTree() delete t; void Initialize(T a, int size, int(*winner)(T a, int b, int c); int

7、 Winner() const return (n) ? t1 : 0; int Winner(int i) const return (i n) ? ti : 0; void RePlay(int i, int(*winner) (T a, int b, int c); void Output() const;WinnerTree類（續(xù)） private: int MaxSize; int n; / current size int LowExt; / lowest-level external nodes int offset; / 2k - 1 int *t; / array for w

8、inner tree T *e; / element array void Play(int p, int lc, int rc, int(*winner)(T a, int b, int c);10.3.3 構(gòu)造函數(shù)templateWinnerTree:WinnerTree(int TreeSize)/ Constructor for winner tree. MaxSize = TreeSize; t = new intMaxSize; n = 0;10.3.4 初始化勝者樹m接受函數(shù)指針winnerq比較兩個(gè)元素間的勝者q用戶提供，可實(shí)現(xiàn)不同的比賽規(guī)則構(gòu)造勝者樹m依次掃描所有外部節(jié)點(diǎn)（選

9、手），調(diào)用Play（比賽）q兩個(gè)外部節(jié)點(diǎn)（或有一個(gè)內(nèi)部節(jié)點(diǎn)）比賽，構(gòu)造出最底層內(nèi)部節(jié)點(diǎn)q若新節(jié)點(diǎn)為其父的右孩子，則與其兄弟比賽，構(gòu)造父節(jié)點(diǎn)左孩子必然已構(gòu)造完重復(fù)此步驟，直至新節(jié)點(diǎn)為左孩子或到達(dá)根節(jié)點(diǎn)（整個(gè)勝者樹構(gòu)造完畢）初始化函數(shù)templatevoid WinnerTree:Initialize(T a, int size, int(*winner)(T a, int b, int c)/ Initialize winner t for array a. if (size MaxSize | size 2) throw BadInput(); n = size; e = a; / compu

10、te s = 2log (n-1) int i, s; for (s = 1; 2*s = n-1; s += s);初始化函數(shù)（續(xù)） LowExt = 2*(n-s); offset = 2*s-1; / play matches for lowest-level external nodes for (i = 2; i = LowExt; i += 2) Play(offset+i)/2, i-1, i, winner);初始化函數(shù)（續(xù)） / handle remaining external nodes if (n % 2) / special case for odd n, play

11、/ internal and external node Play(n/2, tn-1, LowExt+1, winner); i = LowExt+3; else i = LowExt+2; / i is left-most remaining external node for (; i = n; i += 2) Play(i-LowExt+n-1)/2, i-1, i, winner);比賽函數(shù)templatevoid WinnerTree:Play(int p, int lc, int rc, int(*winner)(T a, int b, int c)/ Play matches

12、beginning at tp. / lc and rc are the children of tp. tp = winner(e, lc, rc); / more matches possible if at right child while (p 1 & p % 2) / at a right child tp/2 = winner(e, tp-1, tp); p /= 2; / go to parent 10.3.5 重構(gòu)勝者樹templatevoid WinnerTree:RePlay(int i, int(*winner)(T a, int b, int c)/ Replay m

13、atches for element i. if (i n) throw OutOfBounds(); int p, / match node lc, / left child of p rc; / right child of p / find first match node and its children if (i = 1; p /= 2) tp = winner(e, t2*p, t2*p+1);10.4 敗者樹m勝者樹的重構(gòu)q總是前一次的最終勝者被取代q沿外部節(jié)點(diǎn)根重構(gòu)，需上次比賽敗者與新選手比較q但勝者樹記錄的是勝者，還需訪問孩子節(jié)點(diǎn)重構(gòu)低效例f變?yōu)?找到父節(jié)點(diǎn)1，判斷是否需要

14、修改，需要與e重新比賽，但1保存的是上次的勝者f如果節(jié)點(diǎn)1的結(jié)果改變，則需找到父節(jié)點(diǎn)2，需要與節(jié)點(diǎn)4重新比賽，但2保存的是1而不是41234敗者樹（續(xù)）m內(nèi)部節(jié)點(diǎn)保存敗者，t0最終勝者m重構(gòu)時(shí)，直接提取節(jié)點(diǎn)指向元素，與新元素進(jìn)行比賽f變?yōu)?10.5 應(yīng)用m裝箱（bin packing）問題q若干個(gè)容量為c的箱子和n個(gè)物品q物品i的體積為si（0sic）q可行裝載（feasible packing）：將物品都裝入箱子而不溢出q最優(yōu)裝載（optimal packing）：使用箱子數(shù)目最少的可行裝載裝箱問題應(yīng)用實(shí)例m卡車裝載q運(yùn)輸公司需把包裹裝入卡車，每個(gè)包裹都有一定重量，每輛卡車也有載重限制q希望

15、用最少的卡車來裝載包裹q卡車箱子，包裹物品裝箱問題應(yīng)用實(shí)例m集成片分布q給定寬度的電路板上按行布設(shè)些電路集成片q集成片高度一致但寬度各不相同q電路板的每行箱子，集成片物品q電路板的寬度箱子容量，集成片長度物品體積NP-完全性介紹m不可判定問題（undecidable problem）q停機(jī)問題（halting problem）：令編譯器具有檢查無限循環(huán)的能力q編譯器也是程序，具有檢查無限循環(huán)能力的編譯器很難檢查自身q遞歸不可判定的（recursively undecidable）遞歸不可判定問題m具有檢查無限循環(huán)能力的編譯器q將這個(gè)編譯器程序稱為LOOPq將任意程序P輸入LOOP，LOOP執(zhí)行

16、P，若P無限循環(huán)，LOOP輸出YES，否則LOOP無限循環(huán)q如果將LOOP輸入LOOP，會(huì)怎么樣？如果LOOP(LOOP)停止，則LOOP含無限循環(huán)，矛盾如果LOOP(LOOP)無限循環(huán)，則LOOP應(yīng)停止，矛盾類似“這句話是一句謊話”的矛盾不存在這樣的程序LOOP！確定型和非確定型機(jī)器m確定型機(jī)器：每一時(shí)刻執(zhí)行一條指令，然后下一步執(zhí)行的指令是惟一確定的m非確定型機(jī)器：下一步執(zhí)行的指令是有選擇的，機(jī)器有能力自由選擇導(dǎo)致正確解的指令m前者：目前的標(biāo)準(zhǔn)計(jì)算機(jī)后者：難以實(shí)現(xiàn)的NP類和P類mNP類：非確定型多項(xiàng)式時(shí)間，nondeterministic polynomial-timeP類：確定型多項(xiàng)式時(shí)間

17、，deterministic polynomial-timemP類問題：目前的計(jì)算機(jī)可多項(xiàng)式時(shí)間求解NP類：不知道！問題屬于NP類的檢驗(yàn)m用Yes/No描述問題q多項(xiàng)式時(shí)間內(nèi)，能證明一個(gè)問題的任意“是”的實(shí)例是正確的，則該問題屬于NP類m漢密爾頓圈問題q給定一條路徑，判定它是否漢密爾頓圈m驗(yàn)證答案較之計(jì)算答案容易q是否存在不具有多項(xiàng)式時(shí)間解法的問題尚未發(fā)現(xiàn)m不是所有可判定問題都屬于NP：證明一個(gè)圖沒有漢密爾頓圈NP-完全問題mNP類的子集：NP中最難的問題，NP-completemNP中任一問題都能夠多項(xiàng)式地歸約為NP-完全問題m問題P1歸約為問題P2：存在映射，使得P1的任何實(shí)例都可以變換為

18、P2的實(shí)例NP-完全問題m“最難的”原因q變換NP-完全問題可作為NP中任何問題的子程序，開銷為多項(xiàng)式時(shí)間qNP完全問題存在多項(xiàng)式時(shí)間解，NP中每個(gè)問題必然存在多項(xiàng)式時(shí)間解mP1為NP-完全問題，P2為NP類，若P1可多項(xiàng)式地歸約為P2，P2也是NP-完全問題旅行商問題是NP-完全問題mtraveling salesman problemm問題：給定一完全圖G=(V, E)、邊的權(quán)值以及整數(shù)K，是否存在一個(gè)訪問所有頂點(diǎn)且權(quán)值和=K的簡單圈？m漢密爾頓圈問題是NP-完全問題，且可以多項(xiàng)式地歸約為旅行商問題，因此旅行商問題是NP-完全問題歸約方法m對(duì)圖G，構(gòu)造完全圖G，V=Vm對(duì)(v, w)E，G

19、中其權(quán)值設(shè)定為1，否則設(shè)定為2m另選取K=|V|m則G存在漢密爾頓圈G存在總權(quán)值為|V|的旅行商巡回路線歸約例第一個(gè)NP-完全問題m可滿足性問題（satisfiability）：一個(gè)布爾表達(dá)式作為輸入，要求回答是否可以通過式中變量取值使得表達(dá)式為真m1971年，Cook證明了SAT是NP-完全的qNP中每個(gè)問題都可用一臺(tái)非確定型機(jī)器（圖靈機(jī)）在多項(xiàng)式時(shí)間內(nèi)求解q而此機(jī)器的動(dòng)作可用一個(gè)及其復(fù)雜但仍是多項(xiàng)式的布爾表達(dá)式模擬，表達(dá)式為真圖靈機(jī)輸出為“是”近似解法mNP-完全問題，4種常見近似算法1)最先匹配法（First Fit，F(xiàn)F) 箱子任意排序，依次將物品放入箱子，每個(gè)物品放入第一個(gè)可容納它的

20、箱子2)最優(yōu)匹配法（Best Fit，BF） 數(shù)組Avail保存箱子當(dāng)前可用容量，物品放入可容納它，且Avail值最小的箱子近似解法3)最先匹配遞減法（First Fit Decreasing，F(xiàn)FD） 類似FF，但物品首先按體積遞減順序排序4)最優(yōu)匹配遞減法（Best Fit Decreasing，BFD） 類似BF，但物品首先按體積遞減順序排序mI：裝箱問題實(shí)例，b(I)：最優(yōu)解qFF、BF(17/10)b(I)FFD、BFD(11/9)b(I)+4例10-6m四件物品s1:4=3,5,2,4，箱子容量7qFF，箱子初始容量7, 7, 7, 7物品1放入箱子1，箱子容量4, 7, 7, 7

21、物品2放入箱子2，箱子容量4, 2, 7, 7物品3放入箱子1，箱子容量2, 2, 7, 7物品4需再用一個(gè)箱子共需3個(gè)箱子例10-6qBF物品1放入箱子1，箱子容量4, 7, 7, 7物品2放入箱子2，箱子容量4, 2, 7, 7物品3放入箱子2，箱子容量4, 0, 7, 7物品4又可放入箱子1兩個(gè)箱子qFFD和BFD首先將物品按2、4、1、3排序最后方案均為：使用兩個(gè)箱子，物品2、3放入箱子1；物品1、4放入箱子2例10-6qBF物品1和2分別放入箱子1和箱子2；物品3放入箱子2，物品4又可放入箱子1兩個(gè)箱子qFFD和BFD首先將物品按2、4、1、3排序最后方案均為：使用兩個(gè)箱子，物品2、

22、3放入箱子1；物品1、4放入箱子2利用勝者樹實(shí)現(xiàn)FF和FFDm最多n個(gè)箱子，初始n個(gè)空箱子m所有availj=c，將其作為選手構(gòu)造最大勝者樹m對(duì)每個(gè)物品i，尋找第一個(gè)（最左的）可容納它的箱子利用勝者樹實(shí)現(xiàn)FF和FFD（續(xù)）q從根開始，對(duì)當(dāng)前節(jié)點(diǎn)j，考慮其孩子l、ravailtlsi：左子樹最大可用容量大于等于i的體積有箱子可容納i，轉(zhuǎn)向左子樹繼續(xù)搜索availtrsi：轉(zhuǎn)向右子樹繼續(xù)搜索左、右子樹都無箱子可容納i，失敗q直至外部節(jié)點(diǎn)，將物品放入對(duì)應(yīng)箱子，重構(gòu)勝者樹mQ(nlogn)例s1=8例（續(xù)）s2=6s3=5FirstFit函數(shù)void FirstFitPack(int s, int n

23、, int c)/ Output first fit packing into bins of size c. / n is the number of objects and s their size. WinnerTree *W = new WinnerTree (n); int *avail = new int n+1; / bins / initialize n bins and winner tree for (int i = 1; i Initialize(avail, n, winner);FirstFit函數(shù)（續(xù)） / put objects in bins for (i =

24、1; i = n; i+) / put si in a bin / find first bin with enough capacity int p = 2; / 從根節(jié)點(diǎn)的左孩子開始搜索 while (p Winner(p); if (availwinp si) / 當(dāng)前節(jié)點(diǎn)子樹中無箱子可容納物品i p+ ; / 因此轉(zhuǎn)到它的兄弟父節(jié)點(diǎn)的右子樹繼續(xù)搜索 p *= 2; /轉(zhuǎn)到當(dāng)前節(jié)點(diǎn)的孩子繼續(xù)搜索，也是從左孩子開始 int b; / will be set to bin to use p /= 2; / 當(dāng)前p為外部節(jié)點(diǎn)，轉(zhuǎn)到其父節(jié)點(diǎn)while循環(huán)中 / 最后處理的那個(gè)節(jié)點(diǎn)FirstFit

25、函數(shù)（續(xù)） if (p Winner(p); / b為勝者，可能是右孩子，需檢查箱子b-1（左孩子） / 當(dāng)然b也可能是左孩子，但這種檢查不會(huì)導(dǎo)致錯(cuò)誤 if (b 1 & availb-1 = si) b-; else / p=n：n為奇數(shù)，while最后一次檢查節(jié)點(diǎn)n-1，不能容納i b = W-Winner(p/2); / 轉(zhuǎn)到p(n)外部節(jié)點(diǎn)，需查其父 / 節(jié)點(diǎn)，獲取勝者節(jié)點(diǎn)p在avail中位置 cout Pack object i in bin b RePlay(b, winner); 循環(huán)匹配法mb個(gè)箱子看作一個(gè)環(huán)m物品i放入箱子jm物品i+1從箱子(j+1)%b開始，尋找第一個(gè)可容納它的箱子m若未找到，啟用一個(gè)新箱子，bb+1循環(huán)匹配法例m6個(gè)物