Description

2. Competition Trees. Utilized when we have to break ties in an endorsed mannerTo select the component that was embedded firstTo select the component on the leftLike the load, a competition tree is a finished paired tree that is most productively put away utilizing cluster based parallel treeUsed to get proficient usage of two estimate calculations for the container pressing issue (another NP-difficult problem)T

Transcripts

Competition Trees CSE, POSTECH

Tournament Trees Used when we have to break ties in a recommended way To choose the component that was embedded first To choose the component on the left Like the load, a competition tree is a total parallel tree that is most effectively put away utilizing cluster based twofold tree Used to acquire productive executions of two guess calculations for the canister pressing issue (another NP-difficult issue) Types of competition trees: victor & washout trees

Tournament Trees The competition is played in the sudden-passing mode A player is dispensed with after losing a match Pairs of players play until just a single remains The competition tree is depicted by a double tree Each outer hub speaks to a player Each inside hub speaks to a match played Each level of inner hubs characterizes a round of matches Tournament trees are additionally called determination trees See Figure 13.1 for competition trees

Winner Trees Definition A champ tree for n players is an entire double tree with n outside hubs and n-1 interior hubs. Each inward hub records the victor of the match. To decide the victor of a match, we expect that every player has an incentive In a min ( max ) champ tree, the player with the littler ( bigger ) esteem wins See Figure 13.2 for champ trees

Winner Trees The tallness is log 2 (n+1) (bars the player level) What sort of amusements would utilize (a) min victor tree? What sort of recreations would utilize (b) max victor tree?

Winner Tree Operations Select champ O(1) time to play coordinate at every match hub. Introduce n-1 coordinate hubs O(n) time to instate n-player champ tree Remove victor and replay O(log n) time

Winner Tree Sorting Method Read Example 13.1 Put components to be sorted into a min victor tree. Evacuate the victor and supplant its incentive with a substantial esteem (e.g., ∞). r eplay the matches. If not done, go to step 2.

Sort 16 Numbers 1. Instate the min victor tree

Sort 16 Numbers 2. Evacuate the champ and supplant its esteem

Sort 16 Numbers 3. Replay the matches

Sort 16 Numbers Remove the victor and supplant its esteem

Sort 16 Numbers Replay the matches

Sort 16 Numbers Remove the champ and supplant its esteem

Sort 16 Numbers Replay the matches

Sort 16 Numbers Remove the victor and supplant its esteem Continue in this way… .

Time To Sort Initialize victor tree: O(n) time Remove champ and replay: O(logn) time Remove champ and replay n times : O(nlogn) time Thus, the aggregate sort time is O(nlogn)

Exercise 1 – [3, 5, 6, 7, 20, 8, 2, 9] Max Winner Tree Min Winner Tree After the change, the maximum champ tree gets to be: After the change, the min victor tree gets to be: Is this right?

The ADT WinnerTree Read ADT 13.1 for Winner Tree ADT determination Read Program 13.1 for the conceptual class winnerTree

The Winner Tree Representation Using the cluster representation of a total parallel tree A champ tree of n players requires n-1 inside hubs tree[1:n-1] The players (outer hubs) are spoken to as an exhibit player[1:n] tree[i] is a file into the exhibit player and gives the victor of the match played at hub i See Figure 13.4 for tree-to-exhibit correspondence

Determining the parent of outside hub To execute the interface techniques, we have to decide the parent tree[p] of an outside hub player[i] When the quantity of outer hubs is n , the quantity of inner hubs is n-1 The furthest left interior hub at the most reduced level is numbered s , where s = 2 log2(n-1) The quantity of inward hubs at the least level is n-s , and the number LowExt of outer hubs at the most minimal level is 2*( n-s )

Determining the parent of outer hub What is n and s for Figure 13.4? Let balance = 2*s - 1 . At that point for any outer hub player[i], its parent tree[p] is given by p = (i +offset)/2 i LowExt p = (i – LowExt + n –1)/2 i LowExt

Loser Trees Definition A failure tree for n players is likewise an entire twofold tree with n outside hubs and n-1 inside hubs. Each inner hub records the washout of the match. The general victor is recorded in tree[0] See Figure 13.5 for min washout trees Read Section 13.4

Figure 13.5 Eight-player min failure trees Example Min Loser Trees What isn\'t right with the min washout tree (b)?

Exercise 15 – [20, 10, 12, 18, 30, 16, 35, 33, 45, 7, 15, 19, 33, 11, 17, 25] Max Loser Tree Min Loser Tree After the change, the maximum washout tree gets to be: After the change, the min failure tree gets to be:

Bin Packing Problem We have receptacles that have a limit binCapacity and n questions that should be stuffed into these canisters Object i requires objSize[i], where 0 < objSize[i] binCapacity , units of limit Feasible pressing - a task of articles to containers so that no canister\'s ability is surpassed Optimal pressing - a possible pressing that uses the least number of containers Goal : pack objects with the base number of receptacles The receptacle pressing issue is a NP-difficult issue �� We utilize estimate calculations to take care of the issue

Truck Loading Problem Have packages to pack into trucks Each bundle has a weight Each truck has a heap confine Goal : Minimize the quantity of trucks required Equivalent to the container pressing issue Read Examples 13.4 & 13.5

Bin Packing Approximation Algorithms First Fit (FF) First Fit Decreasing (FFD) Best Fit (BF) Best Fit Decreasing (BFD)

First Fit (FF) Bin Packing Bins are orchestrated in left to correct request. Articles are stuffed each one in turn in a given request. Current question is stuffed into the furthest left container into which it fits. In the event that there is no canister into which current protest fits, begin another container.

Best Fit (BF) Bin Packing Let bin[j].unusedCapacity indicate the limit accessible in canister j Initially, the accessible limit is binCapacity for all containers Object i is stuffed into the receptacle with the slightest unusedCapacity that is in any event objSize[i] If there is no canister into which current question fits, begin another canister.

First Fit Decreasing (FFD) Bin Packing This technique is the same as FF aside from that the articles are requested in a diminishing size so that objSize[i] objSize[i+1], 1 i < n

Best Fit Decreasing (BFD) Bin Packing This strategy is the same as BF with the exception of that the items are requested concerning FFD

Bin Packing Example Assume four items with objSize[1:4] = [3, 5, 2, 4] Assuming every container\'s ability is 7, what might the pressing be in the event that we utilize FF, BF, FFD, or BFD? FF Bin 1: objects 1 & 3, Bin 2: question 2, Bin 3: protest 4 BF Bin 1: objects 1 & 4, Bin 2: objects 2 & 3 FFD Bin 1: objects 2 & 3, Bin 2: objects 1 & 4 BFD Bin 1: objects 2 & 3, Bin 2: objects 1 & 4 Read Example 13.6

First Fit Bin Packing with Max Winner Tree Use a maximum champ tree in which the players are n canisters and the estimation of a player is the accessible limit binCapacity in the container. Perused the segment on First Fit and Winner Trees on pp. 521 & See Figure 13.6 for first-fit (FF) max victor trees See Program 13.2 for the main fit receptacle pressing system

First Fit Bin Packing with Max Winner Tree Example: n=8, binCapacity=10, objSize[] = {8,6,5,3,6,4,2,7} 1 5 1 3 5 7 10 1 2 3 4 5 6 7 8 Initial bin[tree[1]].unusedCapacity >= objSize[1]?

2 5 2 3 5 7 2 10 1 2 3 4 5 6 7 8 After objSize[1]=8 stuffed First Fit Bin Packing with Max Winner Tree Example: n=8, binCapacity=10, objSize[] = {8,6,5,3,6,4,2,7} Where will objSize[2]=6 be pressed into?

3 5 2 3 5 7 2 4 10 1 2 3 4 5 6 7 8 After objSize[2]=6 stuffed First Fit Bin Packing with Max Winner Tree Example: n=8, binCapacity=10, objSize[] = {8,6,5,3,6,4,2,7} Where will objSize[3]=5 be pressed into?

4 5 2 4 5 7 2 4 5 10 1 2 3 4 5 6 7 8 After objSize[3]=5 pressed First Fit Bin Packing with Max Winner Tree Example: n=8, binCapacity=10, objSize[] = {8,6,5,3,6,4,2,7} Where will objSize[4]=3 be stuffed into?

4 5 1 4 5 7 2 1 5 10 1 2 3 4 5 6 7 8 After objSize[4]=3 stuffed First Fit Bin Packing with Max Winner Tree Example: n=8, binCapacity=10, objSize[] = {8,6,5,3,6,4,2,7} Where will objSize[5]=6 be pressed into?

5 3 5 1 3 5 7 2 1 5 4 10 1 2 3 4 5 6 7 8 After objSize[5]=6 pressed First Fit Bin Packing with Max Winner Tree Example: n=8, binCapacity=10, objSize[] = {8,6,5,3,6,4,2,7} Where will objSize[6]=4, objSize[7]=2 and objSize[8]=7 be stuffed into?

More Bin Packing with Max Winner Tree Exercise – Do a similar case utilizing BF, FFD, BFD with Max Winner Tree Do Exercise 13.23 READ Chapter 13