PruningExponential growthSlide 3Sum of subsetsBrute forceBinary tree representationDetecting nonpromising nodesStill exponentialBoolean satisfactionIntractable problemsThe EndJan 14, 2019Pruning2Exponential growthHow many leaves are there in a complete binary tree of depth N?This is easy to demonstrate:Count “going left” as a 0Count “going right” as a 1Each leaf represents one of the 2N possible N-bit binary numbersThis observation turns out to be very useful in certain kinds of problemsdepth = 0, count = 1 depth = 1, count = 2 depth = 3, count = 4 depth = 4, count = 8 depth = 5, count = 16 depth = N, count = 2N3PruningSuppose the binary tree represents a problem that we have to explore to find a solution (or goal node)If we can prune (decide we can ignore) a part of the tree, we save effortThe higher up in the tree we can prune, the more effort we can saveThe advantage is exponentialsaves 3saves 7saves 154Sum of subsetsProblem:There are n positive integers, and a positive integer WFind a subset of the integers that sum to exactly WExample:The numbers are 2, 5, 7, 8, 13Find a subset of numbers that sum to exactly 25We can multiply each number by 1 if it is in the sum, 0 if it is not2 5 7 8 130 0 0 0 0 00 0 0 0 1 130 0 0 1 0 80 0 0 1 1 210 0 1 0 1 200 0 1 1 0 150 0 1 1 1 280 1 0 0 0 50 1 0 0 1 180 1 0 1 0 130 1 0 1 1 260 1 1 0 0 120 1 1 0 1 255Brute forceWe have a brute-force method for solving the sum of subsets problemFor N numbers, count in binary from 0 to 2NFor each 1, include the corresponding number; for each 0, exclude the corresponding numberStop if we get luckyThis is clearly an exponential-time algorithmIt seems like, with a little cleverness, we could do betterIt turns out that we can use pruning to do somewhat betterBut we are still left with an exponential-time algorithm6Binary tree representationSuppose our numbers are3, 8, 9, 17, 26, 39, 43, 56and our goal is 100We can describe thisas a binary tree searchAs we search the binary tree,A node is promising if we might be able to get to a solution from itA node is nonpromising if we know we can’t get to a solutionWhen we detect a nonpromising node, we can prune (ignore) the entire subtree rooted at that nodeHow do we detect nonpromising nodes? 3 (yes or no) 8 (yes or no) 9 (yes or no) 17 (yes or no) etc.7Detecting nonpromising nodesSuppose we work from left to right in the sequence 3 8 9 17 26 39 43 56That is, we try things in the order 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 ...When we get to 0 0 0 0 0 0 1 0 43we notice that even if we include all the remaining numbers (in this case, there is only one), we can’t get to 100There is no need to try the 0 0 0 0 0 0 1 x numbersWhen we get to 1 1 1 1 1 1 0 0 101we notice that we have overshot, hence no solution is possible with what we have so farWe don’t need to try any of the 1 1 1 1 1 1 x x numbers8Still exponentialEven with pruning, the sum of subsets typically requires exponential timeHowever, in some cases, pruning can save significant amounts of timeConsider trying to find a subset of {23, 29, 35, 41, 43, 46, 48, 51} that sums to 100Here, pruning can save substantial effortSometimes, common sense can be a big helpConsider trying to find a subset of {16, 20, 28, 34, 44, 48} that sums to 759Boolean satisfactionSuppose you have n boolean variables, a, b, c, ..., that occur in a logical expression such as (a or c or not f) and (not b or not d or a) and ...The problem is to assign true/false values to each of the boolean variables in such a way as to satisfy (make true) the logical expressionThe brute-force algorithm is the same as before (0 is false, 1 is true, try all n binary numbers)Again, you can do significant pruning, if you think about the problemAnything you do, you will still end up with a solution that is exponential in n10Intractable problemsThe technical term for a problem that takes exponential time is intractableIntractable problems can only be solved for small input sizesFaster computer speeds will not help much—exponential growth is fastBottom line: Avoid these problems if at all possible!11The
View Full Document