Transcript ppt - HKOI
Exhaustion, Branch and Bound Gary Wong If you have any question, please ask via Email: [email protected] MSN: [email protected] Welcome! • Your 1st training on advanced topics this year • I assume you have sufficient basic knowledge Pre-requisites • Recursion • Basic concepts of permutation and combination • Graph Searching (Optional) Exhaustion • Check for (almost) all possible cases • Advantages – Simple – Correct in nearly all circumstances • Provided that you implement correctly • Disadvantages – Can be too slow if too many cases (e.g. exponential) – Implementation is sometimes difficult When do we use exhaustion? • Not many possible cases • No other better methods are in your mind – Might not be your fault! – Many computational problems in the world have no known polynomial-time solutions – P, NP, NP-hard, NP-completeness… • Usually when the constraints are very small, you should think about whether exhaustion is possible Let me count the ways • Now you have unlimited supply of coins of values 1, 5, 10, 25 and 50 cents • Find the number of ways to make up n cents • 0 <= n <= 99 Let me count the ways • Have a rough (and conservative) estimation on number of possible cases • If only 1 cent can be used, at most how many coins? • If only 5 cents can be used, at most how many coins? • … • A very rough upper bound: – 100 x 20 x 10 x 4 x 2 = 1600000 • Surely acceptable within 1s Grid • Given an N x N white grids (N <= 5) • You may toggle the grid colors like this (white -> black; black -> white): • Given the initial colors of the grids, find the minimum number of toggling required to make all grids to become black Grid • Observations: – Toggle twice = Not toggle at all – Sequence of toggling does not affect the final appearance of the board – How many possible sequences of toggling are there? • Time Complexity: O(2NxN) • A more efficient algorithm actually exists! • Hint: its time complexity is O(2N x N2) Magic triangle • Given a magic triangle of N layers (1 <= N <= 5), comprising of N(N+1)/2 nodes • Integers 1 to N(N+1)/2 are assigned into each node exactly once, such that: – The number in a node = absolute difference of the numbers in its two children nodes • M numbers (0 <= M <= N(N+1)/2) have filled into some nodes, fill in the remaining nodes 1 • Time limit: 1s 4 6 2 3 5 Magic triangle • Let’s fill in the N(N+1)/2 numbers into the circles! • O((N(N+1)/2 – M)!) • Worst case? – N=5 – M = 0, i.e. no numbers are filled – 15! = 1307674368000 Magic triangle – 2nd attempt • Observation: – Numbers in lower layers can be used to derive the numbers above! – Why not just exhausting the lowest layer? • Time complexity: O(TPN), where T = N(N+1)/2 • 15P5 = 15! / 10! = 360360 What have you learnt? • Smart exhaustion vs Stupid exhaustion • Now I would teach you what “smart” means… A Classical Problem – Bin Packing • A number of objects are to be put into some identical bins • Find the minimum number of bins required to pack all objects Capacity: 50 10 20 30 50 20 Solution 1 • S = Sum of volumes of all objects • C = Capacity of a container • Answer = ceil (S / V) • Wrong! • Why? Solution 2 • Sort the objects in ascending order of their volumes • Put the smaller objects first • Wrong! • Why? The correct solution • Exhaustion BIN PACKING() if All objects have been put in some bins then update the best solution if a better one is found pick a bin B for each object O do if volume of O does not exceed remaining space in B then Put O into B BIN PACKING() Remove O from B Search tree Empty bins B1(50) B1(10) … B1(20) … B1(10,20) B1(50); B2(10) • DFS • For N objects, O(N!) … The cruel reality • N <= 40 • Performance: – input1.txt: Accepted – input2.txt: Accepted – input3.txt: TLE • How to speed up? Back to the search tree… • Is it necessary to go further here? Why? Empty bins B1(50) B1(10) … … B1(10,20) B1(50); B2(10) Suppose you know here that at most 2 bins are needed B1(20) … Optimization • Tree Pruning (Branch and Bound!) • Suppose f is the solution at this moment • If f >= cur_best, do not go further • Performance: – input1.txt: Accepted – input2.txt: Accepted – input3.txt: TLE • Still too slow… • Can we do better? A* Search • Let h be an estimated lower bound for the number of bins required to pack all unpacked objects • If f + h >= best, do not go further • h is also known as a heuristic function • But what makes a good function h in this case? The cruel reality, again • Performance: – – – – input1.txt: Accepted input2.txt: Accepted input3.txt: Accepted input4.txt: TLE • Further improved now • Can we do even better? Equivalent configurations = = Avoid equivalent configurations • Sort the objects by their volumes before searching • When putting the objects, you should ensure that: – The volumes of objects in each bin are in non-decreasing order, or – The volumes of smallest objects in all bins form a nonincreasing order A happy ending • Performance: – – – – – – – – input1.txt: Accepted input2.txt: Accepted input3.txt: Accepted input4.txt: Accepted input5.txt: Accepted input6.txt: Accepted input7.txt: Accepted input8.txt: Accepted • Result: Accepted Summary • Tree Pruning • A* • Avoid equivalent configurations Exercises • • • • • 1049 Chocolate 1050 Bin Packing 2005 Magic Triangle 2065 Toggle 3031 Trishade