




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
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. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 智慧教育平台下的教学模式创新
- 智慧城市大数据管理与隐私保护的未来趋势
- 教育资源优化配置在中医教学中的实践研究
- 全球化背景下的教育创新课程设计
- 营养膳食培训课件
- 智慧教育中的数字资源均衡分配方案
- 教育大数据库的构建与个性化学习方案设计实践
- 中国南方航空接送机理论培训
- 抖音商户达人合作流程标准化制度
- 抖音商户编导短视频传播潜力评估制度
- 动设备监测课件 转动设备状态监测与故障诊断
- 小龙虾啤酒节小龙虾啤酒音乐节活动策划方案
- 植物分类完整版本
- 医院培训课件:《复用器械之预处理》
- 【MOOC】犯罪心理学-中南财经政法大学 中国大学慕课MOOC答案
- 彩钢瓦拆除施工方案
- 儿童静脉治疗循证指南
- 2024年11月江苏南京市建邺区政府购岗人员招聘12人备考题库500题及答案解析
- 学校安保服务方案(技术方案)
- 人教版2024年六年级语文下册期末考试摸底检测
- 西南民族大学:人工智能赋能课程建设的逻辑与路径
评论
0/150
提交评论