DOC PREVIEW
Penn CIT 594 - Pruning

This preview shows page 1-2-3-4 out of 11 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

PruningExponential growthSlide 3Sum of subsetsBrute forceBinary tree representationDetecting nonpromising nodesStill exponentialBoolean satisfactionIntractable problemsThe EndJan 14, 2019Pruning2Exponential growthHow many leaves are there in a complete binary tree of depth N?This is easy to demonstrate:Count “going left” as a 0Count “going right” as a 1Each leaf represents one of the 2N possible N-bit binary numbersThis 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 = 2N3PruningSuppose 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 effortThe higher up in the tree we can prune, the more effort we can saveThe advantage is exponentialsaves 3saves 7saves 154Sum of subsetsProblem:There are n positive integers, and a positive integer WFind a subset of the integers that sum to exactly WExample:The numbers are 2, 5, 7, 8, 13Find a subset of numbers that sum to exactly 25We can multiply each number by 1 if it is in the sum, 0 if it is not2 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 forceWe have a brute-force method for solving the sum of subsets problemFor N numbers, count in binary from 0 to 2NFor each 1, include the corresponding number; for each 0, exclude the corresponding numberStop if we get luckyThis is clearly an exponential-time algorithmIt seems like, with a little cleverness, we could do betterIt turns out that we can use pruning to do somewhat betterBut we are still left with an exponential-time algorithm6Binary tree representationSuppose our numbers are3, 8, 9, 17, 26, 39, 43, 56and our goal is 100We can describe thisas a binary tree searchAs we search the binary tree,A node is promising if we might be able to get to a solution from itA node is nonpromising if we know we can’t get to a solutionWhen we detect a nonpromising node, we can prune (ignore) the entire subtree rooted at that nodeHow do we detect nonpromising nodes? 3 (yes or no) 8 (yes or no) 9 (yes or no) 17 (yes or no) etc.7Detecting nonpromising nodesSuppose we work from left to right in the sequence 3 8 9 17 26 39 43 56That 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 100There is no need to try the 0 0 0 0 0 0 1 x numbersWhen 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 farWe don’t need to try any of the 1 1 1 1 1 1 x x numbers8Still exponentialEven with pruning, the sum of subsets typically requires exponential timeHowever, in some cases, pruning can save significant amounts of timeConsider trying to find a subset of {23, 29, 35, 41, 43, 46, 48, 51} that sums to 100Here, pruning can save substantial effortSometimes, common sense can be a big helpConsider trying to find a subset of {16, 20, 28, 34, 44, 48} that sums to 759Boolean satisfactionSuppose 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 expressionThe 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 problemAnything you do, you will still end up with a solution that is exponential in n10Intractable problemsThe technical term for a problem that takes exponential time is intractableIntractable problems can only be solved for small input sizesFaster computer speeds will not help much—exponential growth is fastBottom line: Avoid these problems if at all possible!11The


View Full Document

Penn CIT 594 - Pruning

Documents in this Course
Trees

Trees

17 pages

Searching

Searching

24 pages

Arrays

Arrays

17 pages

Stacks

Stacks

30 pages

Recursion

Recursion

25 pages

Hashing

Hashing

24 pages

Recursion

Recursion

24 pages

Graphs

Graphs

25 pages

Storage

Storage

37 pages

Trees

Trees

21 pages

Arrays

Arrays

24 pages

Hashing

Hashing

24 pages

Recursion

Recursion

25 pages

Graphs

Graphs

23 pages

Graphs

Graphs

25 pages

Stacks

Stacks

25 pages

Recursion

Recursion

25 pages

Quicksort

Quicksort

21 pages

Quicksort

Quicksort

21 pages

Graphs

Graphs

25 pages

Recursion

Recursion

25 pages

Searching

Searching

24 pages

Counting

Counting

20 pages

HTML

HTML

18 pages

Recursion

Recursion

24 pages

Pruning

Pruning

11 pages

Graphs

Graphs

25 pages

Load more
Download Pruning
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Pruning and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Pruning 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?