lec05

Views:
 
Category: Education
     
 

Presentation Description

No description available.

Comments

Presentation Transcript

Tournament Trees: 

Tournament Trees Winner trees. Loser Trees.

Winner Tree – Definition: 

Winner Tree – Definition Complete 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. Root has overall winner.

Winner Tree For 16 Players: 

Winner Tree For 16 Players

Winner Tree For 16 Players: 

Winner Tree For 16 Players 4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8 Smaller element wins => min winner tree. 3 6 1 3 2 4 2 5 3 1 2 2 1 2 1

Winner Tree For 16 Players: 

Winner Tree For 16 Players 4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8 height is log2 n (excludes player level) 3 6 1 3 2 4 2 5 3 1 2 2 1 2 1

Complexity Of Initialize: 

Complexity Of Initialize O(1) time to play match at each match node. n – 1 match nodes. O(n) time to initialize n-player winner tree.

Winner Tree Operations: 

Winner Tree Operations Initialize O(n) time Get winner O(1) time Replace winner and replay O(log n) time More precisely Theta(log n) Tie breaker (player on left wins in case of a tie).

Replace Winner And Replay: 

Replace Winner And Replay Replace winner with 6.

Replace Winner And Replay: 

Replace Winner And Replay 4 3 6 8 6 5 7 3 2 6 9 4 5 2 5 8 3 6 1 3 2 4 2 5 3 1 2 2 1 2 1 Replay matches on path to root.

Replace Winner And Replay: 

Replace Winner And Replay 4 3 6 8 6 5 7 3 2 6 9 4 5 2 5 8 3 6 1 3 2 4 2 5 3 1 2 2 1 2 1 Replay matches on path to root.

Replace Winner And Replay: 

Replace Winner And Replay 4 3 6 8 6 5 7 3 2 6 9 4 5 2 5 8 3 6 1 3 2 4 2 5 3 1 2 2 1 2 1 Opponent is player who lost last match played at this node.

Loser Tree: 

Loser Tree Each match node stores the match loser rather than the match winner.

Min Loser Tree For 16 Players: 

Min Loser Tree For 16 Players 4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8 4 3 8

Min Loser Tree For 16 Players: 

Min Loser Tree For 16 Players 4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8 4 6 8 3 5 1 7

Min Loser Tree For 16 Players: 

Min Loser Tree For 16 Players 4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8 4 6 8 3 5 3 7 1 6 2 9

Min Loser Tree For 16 Players: 

Min Loser Tree For 16 Players 4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8 4 6 8 3 5 3 7 2 5 2 8 1 6 4 9

Min Loser Tree For 16 Players: 

Min Loser Tree For 16 Players 4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8 4 6 8 3 5 3 7 2 5 5 8 1 6 4 9

Min Loser Tree For 16 Players: 

Min Loser Tree For 16 Players 4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8 4 6 8 3 5 3 7 2 5 5 8 1 6 4 9

Min Loser Tree For 16 Players: 

Min Loser Tree For 16 Players 4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8 4 6 8 3 5 3 7 2 5 5 8 2 6 4 9

Slide20: 

4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8 4 6 8 3 5 3 7 2 5 5 8 2 6 4 9 1 Winner

Complexity Of Loser Tree Initialize: 

Complexity Of Loser Tree Initialize Start with 2 credits at 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).

Slide22: 

Winner Replace winner with 9 and replay matches.

Complexity Of Replay: 

Complexity Of Replay One match at each level that has a match node. O(log n) More precisely Theta(log n).

Tournament Tree Applications: 

Tournament Tree Applications Run generation. k-way merging of runs during an external merge sort. Truck loading.

Truck Loading: 

Truck Loading n packages to be loaded into trucks each package has a weight each truck has a capacity of c tons minimize number of trucks

Bin Packing: 

Bin Packing n items to be packed into bins each item has a size each bin has a capacity of c tons minimize number of bins

Bin Packing: 

Bin Packing Truck 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.

Bin Packing Heuristics: 

Bin Packing Heuristics First 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 Heuristics: 

Bin Packing Heuristics First Fit Decreasing. Items are sorted into decreasing order. Then first fit is applied.

Bin Packing Heuristics: 

Bin Packing Heuristics Best 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.

Bin Packing Heuristics: 

Bin Packing Heuristics Best Fit Decreasing. Items are sorted into decreasing order. Then best fit is applied.

Performance: 

Performance For first fit and best fit: Heuristic Bins <= (17/10)(Minimum Bins) + 2 For first fit decreasing and best fit decreasing: Heuristic Bins <= (11/9)(Minimum Bins) + 4

Max Winner-Tree For 16 Bins: 

Max Winner-Tree For 16 Bins Item size = 7

Max Winner-Tree For 16 Bins: 

7 1 Max Winner-Tree For 16 Bins 6 4 3 6 1 5 7 3 2 6 9 4 5 2 5 8 4 6 5 7 6 9 5 8 7 9 8 9 9

Complexity Of First Fit: 

Complexity Of First Fit O(n log n), where n is the number of items.

authorStream Live Help