版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、Tournament TreesWinner trees.Loser Trees.Winner Tree DefinitionComplete binary tree with n external nodes and n 1 internal nodes.External nodes represent tournament players.Each internal node represents a match played between its two children; the winner of the match is stored at the internal node.R
2、oot has overall winner.Winner Tree For 16 Playersplayermatch nodeWinner Tree For 16 Players4368157326945258Smaller element wins = min winner tree.361324253122121Winner Tree For 16 Players4368157326945258height is log2 n (excludes player level)361324253122121Complexity Of InitializeO(1) time to play
3、match at each match node.n 1 match nodes.O(n) time to initialize n-player winner tree.Winner Tree OperationsInitializeO(n) timeGet winnerO(1) timeReplace winner and replayO(log n) time More precisely Theta(log n)Tie breaker (player on left wins in case of a tie).Replace Winner And Replay436815732694
4、5258361324253122121Replace winner with 6.Replace Winner And Replay4368657326945258361324253122121Replay matches on path to root.Replace Winner And Replay4368657326945258361324253122121Replay matches on path to root.Replace Winner And Replay4368657326945258361324253122121Opponent is player who lost l
5、ast match played at this node.Loser TreeEach match node stores the match loser rather than the match winner.Min Loser Tree For 16 Players4368157326945258438Min Loser Tree For 16 Players43681573269452584683517Min Loser Tree For 16 Players436815732694525846835371629Min Loser Tree For 16 Players4368157
6、326945258468353725281649Min Loser Tree For 16 Players4368157326945258468353725581649Min Loser Tree For 16 Players4368157326945258468353725581649Min Loser Tree For 16 Players436815732694525846835372558264943681573269452584683537255826491WinnerComplexity Of Loser Tree InitializeStart with 2 credits at
7、 each node.Use one to pay for the match played at that node.Use the other to pay for the store of a left child winner.Total time is O(n).More precisely Theta(n).Winner43681573269452584683537255826491Replace winner with 9 and replay matches.959332Complexity Of ReplayOne match at each level that has a
8、 match node.O(log n)More precisely Theta(log n).Tournament Tree ApplicationsRun generation.k-way merging of runs during an external merge sort.Truck loading.Truck Loadingn packages to be loaded into truckseach package has a weighteach truck has a capacity of c tonsminimize number of trucksBin Packin
9、gn items to be packed into binseach item has a sizeeach bin has a capacity of c tonsminimize number of binsBin PackingTruck loading is same as bin packing.Truck is a bin that is to be packed (loaded).Package is an item/element.Bin packing to minimize number of bins is NP-hard.Several fast heuristics
10、 have been proposed.Bin Packing HeuristicsFirst Fit.Bins are arranged in left to right order.Items are packed one at a time in given order.Current item is packed into leftmost bin into which it fits.If there is no bin into which current item fits, start a new bin.Bin Packing HeuristicsFirst Fit Decr
11、easing.Items are sorted into decreasing order.Then first fit is applied.Bin Packing HeuristicsBest Fit.Items are packed one at a time in given order.To determine the bin for an item, first determine set S of bins into which the item fits.If S is empty, then start a new bin and put item into this new
12、 bin.Otherwise, pack into bin of S that has least available capacity.Bin Packing HeuristicsBest Fit Decreasing.Items are sorted into decreasing order.Then best fit is applied.PerformanceFor first fit and best fit:Heuristic Bins = (17/10)(Minimum Bins) + 2For first fit decreasing and best fit decreasing:Heuristic Bins = (11/9)(Minimum Bins) + 4Max
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- (4)相交線與平行線(B卷)-七年級(jí)數(shù)學(xué)冀教版暑假作業(yè)(含答案)
- 中國(guó)農(nóng)民豐收節(jié)專題慶?;顒?dòng)方案模板
- 合同法定解除條件適用的相關(guān)研究
- 《1 例伴有濕疹的肺癌患者 PICC 置管后靜脈炎的護(hù)理》
- 2021-2022學(xué)年廣東省廣州市越秀區(qū)六年級(jí)(上)期末語(yǔ)文試卷
- 四六級(jí)真題十年必考100個(gè)單詞
- 細(xì)胞生活的環(huán)境(簡(jiǎn) 潔版) 高二上學(xué)期生物人教版(2019)選擇性必修1
- 大學(xué)美育 課件 第二篇第三章第三節(jié) 自強(qiáng)不息
- Welcome+Unit+Reading+and+Thinking+學(xué)歷案 高一上學(xué)期英語(yǔ)人教版(2019)必修第一冊(cè)
- 冠詞 高三英語(yǔ)上學(xué)期一輪復(fù)習(xí)專項(xiàng)
- 醫(yī)療技術(shù)培訓(xùn)
- 消防管道跨越建筑伸縮縫的做法詳解
- 《計(jì)算凝聚態(tài)物理》課件
- 憲法學(xué)講義(完整版)
- 2023-2024學(xué)年四川省成都市石室天府中學(xué)英語(yǔ)九年級(jí)第一學(xué)期期末聯(lián)考模擬試題含解析
- 感染性休克查房
- 代辦采礦證協(xié)議
- 小米多元化戰(zhàn)略研究
- 2023電化學(xué)儲(chǔ)能電站消防安全技術(shù)
- 中醫(yī)跟師總結(jié)論文3000字(通用3篇)
- 徐州工程學(xué)院空調(diào)投標(biāo)書
評(píng)論
0/150
提交評(píng)論