资源描述
Tournament TreesWinner trees.Loser Trees.2004-31L.ChenWinner Tree nComplete binary tree with n external nodes and n 1 internal nodes.nExternal nodes represent tournament players.nEach internal node represents a match played between its two children;the winner of the match is stored at the internal node.nRoot has overall winner.2004-32L.ChenWinner Tree For 16 Playersplayermatch node2004-33L.ChenWinner Tree For 16 Players4368157326945258Smaller element wins=min winner tree.3613242531221212004-34L.ChenWinner Tree For 16 Players4368157326945258height is log2 n(excludes player level)3613242531221212004-35L.ChenComplexity Of InitializenO(1)time to play match at each match node.nn 1 match nodes.nO(n)time to initialize n player winner tree.2004-36L.ChenWinner Tree OperationsnInitializeO(n)timenGet winnerO(1)timenRemove winner and replayO(log n)time More precisely Theta(log n)Tie breaker(player on left wins in case of a tie).2004-37L.ChenReplace Winner And Replay4368157326945258361324253122121Replace winner with 6.2004-38L.ChenReplace Winner And Replay4368657326945258361324253122121Replay matches on path to root.2004-39L.ChenReplace Winner And Replay4368657326945258361324253122121Replay matches on path to root.2004-310L.ChenReplace Winner And Replay4368657326945258361324253122121Opponent is player who lost last match played at this node.2004-311L.ChenLoser TreenEach match node stores the match loser rather than the match winner.2004-312L.ChenMin Loser Tree For 16 Players43681573269452584382004-313L.ChenMin Loser Tree For 16 Players436815732694525846835172004-314L.ChenMin Loser Tree For 16 Players4368157326945258468353716292004-315L.ChenMin Loser Tree For 16 Players43681573269452584683537252816492004-316L.ChenMin Loser Tree For 16 Players43681573269452584683537255816492004-317L.ChenMin Loser Tree For 16 Players43681573269452584683537255816492004-318L.ChenMin Loser Tree For 16 Players43681573269452584683537255826492004-319L.Chen43681573269452584683537255826491Winner2004-320L.ChenComplexity Of Loser Tree InitializenOne match at each match node.nOne store of a left child winner.nTotal time is O(n).nMore precisely Theta(n).2004-321L.ChenWinner43681573269452584683537255826491Replace winner with 9 and replay matches.9593322004-322L.ChenComplexity Of ReplaynOne match at each level that has a match node.nO(log n)nMore precisely Theta(log n).2004-323L.ChenApplicationsTournament Tree:nRun generation.nk-way merging of runs during an external merge sort.nTruck loading.2004-324L.ChenTruck Loadingn packages to be loaded into truckseach package has a weighteach truck has a capacity of c tonsminimize number of trucks2004-325L.ChenBin Packingn items to be packed into binseach item has a sizeeach bin has a capacity of c tonsminimize number of bins2004-326L.ChenBin 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 have been proposed.2004-327L.ChenBin Packing HeuristicsnFirst 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.2004-328L.ChenFirst Fitn=4weights=4,7,3,6capacity=10Pack red item into first bin.2004-329L.ChenFirst Fitn=4weights=4,7,3,6capacity=10Pack blue item next.Doesnt fit,so start a new bin.2004-330L.ChenFirst Fitn=4weights=4,7,3,6capacity=102004-331L.ChenFirst Fitn=4weights=4,7,3,6capacity=10Pack yellow item into first bin.2004-332L.ChenFirst Fitn=4weights=4,7,3,6capacity=10Pack green item.Need a new bin.2004-333L.ChenFirst Fitn=4weights=4,7,3,6capacity=10Not optimal.2 bins suffice.2004-334L.ChenBin Packing HeuristicsnFirst Fit Decreasing.Items are sorted into decreasing order.Then first fit is applied.2004-335L.ChenBin Packing HeuristicsnBest 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 bin.Otherwise,pack into bin of S that has least available capacity.2004-336L.ChenBin Packing HeuristicsnBest Fit Decreasing.Items are sorted into decreasing order.Then best fit is applied.2004-337L.ChenPerformancenFor first fit and best fit:Heuristic Bins=(17/10)(Minimum Bins)+2nFor first fit decreasing and best fit decreasing:Heuristic Bins=(11/9)(Minimum Bins)+42004-338L.ChenMax Winner-Tree For 16 Bins8436815732694525848576958798899Item size=72004-339L.Chen71Max Winner-Tree For 16 Bins643615732694525846576958798992004-340L.ChenComplexity Of First FitO(n log n),where n is the number of items.2004-341L.ChenApplicationsSorting.Put elements to be sorted into a winner tree.Repeatedly extract the winner and replace by a large value.2004-342L.ChenSort 16 Numbers43681573269452583613242531221212004-343L.ChenSort 16 Numbers43681573269452583613242531221212004-344L.ChenSort 16 Numbers4368157326945258361324253122121Sorted array.12004-345L.ChenSort 16 Numbers4368157326945258365324253122121Sorted array.12004-346L.ChenSort 16 Numbers4368157326945258363532425322121Sorted array.12004-347L.ChenSort 16 Numbers4368157326945258363532425322321Sorted array.12004-348L.ChenSort 16 Numbers4368157326945258363532425322322Sorted array.12004-349L.ChenSort 16 Numbers4368157326945258363532425322322 22Sorted array.122004-350L.ChenSort 16 Numbers4368157326945258363536425322322 22Sorted array.122004-351L.ChenSort 16 Numbers4368157326945258363536425342322 22Sorted array.122004-352L.ChenSort 16 Numbers4368157326945258363536425342322 22Sorted array.122004-353L.ChenSort 16 Numbers4368157326945258363536425342322 22Sorted array.122004-354L.ChenSort 16 Numbers4368157326945258363536425342322Sorted array.1222004-355L.ChenSort 16 Numbers4368157326945258363536455342322Sorted array.1222004-356L.ChenSort 16 Numbers4368157326945258363536455345322Sorted array.1222004-357L.ChenSort 16 Numbers4368157326945258363536455345342Sorted array.1222004-358L.ChenSort 16 Numbers4368157326945258363536455345343Sorted array.1222004-359L.ChenSort 16 Numbers4368157326945258363536455345343Sorted array.12232004-360L.ChenTime To SortnInitialize winner tree.O(n)timenRemove winner and replay.O(log n)timenRemove winner and replay n times.O(n log n)timenTotal sort time is O(n log n).nActually Theta(n log n).2004-361L.ChenWinner Tree OperationsnInitializeO(n)timenGet winnerO(1)timenRemove/replace winner and replayO(log n)time more precisely Theta(log n)2004-362L.ChenReplace Winner And Replay4368157326945258361324253122121Replace winner with 6.2004-363L.ChenReplace Winner And Replay4368657326945258361324253122121Replay matches on path to root.2004-364L.ChenReplace Winner And Replay4368657326945258361324253122121Replay matches on path to root.2004-365L.ChenReplace Winner And Replay4368657326945258361324253122121Opponent is player who lost last match played at this node.2004-366L.ChenMore Tournament Tree Applicationsnk-way merging of runs during an external merge sortnTruck loading2004-367L.ChenExercisesChapter Ex;Ex;Ex;Ex;Ex2004-368L.Chen谢谢！
展开阅读全文