Problem Solving: Brute Force Approaches

Problem Solving: Brute Force Approaches

Problem Solving: Brute Force Approaches Brute Force Approaches (aka Complete Search) Basic idea: try out everything to find the best. Sometimes, this is the only reasonable solution Given an unsorted list of numbers, find the max/min. Only option is to look at each number. Sometimes, the brute-force approach is good enough Especially when sizes are not too large, or time is not an issue e.g. if checking n! different options, if n is 3 or 4, it might be fine to enumerate them.

Often, the brute-force approach is the easiest to implement Unless you expect time to be an issue (which it often is), its a good way to start Solving via brute force ensures you understand the problem and know a way to find a solution If you know a brute force solution is correct, you can use it as a check on your faster solution Basic ways to approach brute force Iterative vs. recursive Iterative: loop through to generate all possible combinations Sometimes will need many loops Recursive: Make choices in order, generating next state Then use backtracking to return to previous state and pick next choice

Generative vs. filtered Generators: generate the possible answers the good ones Often a recursive definition is better, here Filtered: generate all answers and choose valid ones Common Themes to Brute-Force Approaches Pruning When exploring an option, quit that example as soon as you know it cant work. Bounds Limitations

Check the limitations on sizes of input, or other factors This can drastically reduce the search space of possible options Iterative approaches Loop through all options, testing each Example: find all pairs of numbers where X is c times Y, and X and Y are 5-digit numbers, using all digits from 0-9 Multiple loops Example: enumerate all subsets of 6 numbers from a larger collection; use 6 nested loops Limit range of search If x2+y2+z2 = C, then x, y, z must have absolute value < sqrt(C), etc. Keep flag to stop loops early (pruning)

Generating all permutations Example: For 8 moviegoers, what seating options in a row meet all of 20 conditions (setting limits about distance apart/near) Subset-sum Generate all subsets, then check those n items, 2n possible subsets; possibly viable for n<=20 Example Read numbers A, B C, each <= 10000. Find distinct x, y, z so that: x+y+z = A x*y*z = B x2+y2+z2 = C

We can limit loops to [-100,100] for each, due to C We can limit one of these to cube root of B, or [-22,22] at most We can do fast checks to make sure x, y, z are distinct before doing calculations Then, just have loops, and check answers. Recursive search Recursively search for all possible solutions to a problem Key is to prune away invalid solutions quickly Classical problem: 8 queens Find the positions possible for arranging 8 queens on a chessboard so they cant attack each other First: note each column must have one queen, so can recurse that way Check each row for that column to see if valid if so, place and recurse (for each valid position)

Valid position means not at the same row or on same diagonal as a prior queen Helps prune away large sections of search space. Expanded problem: n-queens on larger board Need faster (e.g. bitfield) storage to identify valid/invalid rows/diagonals. Notice: 2n-1 left and 2n-1 right diagonals on an nxn board. Tips to improve performance of brute force Use short-circuiting of if statements to limit checks Symmetries: Can drastically reduce the search space. But, can involve a lot of overhead and complicate the code Pre-compute: When some values can be known ahead of time,

precompute and store. Solve backward: Look at whether the inverse problem is faster Optimize source code: First, try to identify the critical code (see next page) Optimizing source code Use a faster language: C++>Java>Python Faster I/O: C++: scanf/printf vs. cin/cout (scanf/printf dont flush other) Java: BufferedReader/BufferedWriter vs. Scanner/PrintStream Use built-in fast sort (e.g. C++ algorithm::sort) Access 2D arrays in row-major order (for cache coherency)

Use bit manipulations whenever possible Use low-level structures when you know you dont need advanced functionality e.g. arrays vs. vectors, char[] vs. string Do single allocation of array as a global Locals avoid passing/copying Dynamic allocation will take time Iterative instead of recursive code when possible Avoid repeated array access store the data in a variable Brute Force in Book Book references section 3.2 READ THIS CHAPTER!!!

Examples of basic problem solutions Generating all permutations Use the C++ next_permutation algorithm (iterative approach to generating permutations!). Generating all subsets Form an n-bit bitmask (integer), then iterate through numbers

Recently Viewed Presentations

  • 1 Understanding the US-China Trade Relationship On balance,

    1 Understanding the US-China Trade Relationship On balance,

    Understanding the US-China Trade Relationship. Many Americans have been told that international trade—and more specifically, China's trade relationship with the United States—is bad for workers and hurts US growth. Some American jobs have been lost. ... PowerPoint Presentation Last ...
  • Science Today

    Science Today

    5. Their beaks were different. 6. obtaining food. 7. D. 8. C. 9. The finches were descended from South American finches blown to the islands by a storm. Over many generations, the finches adapted to life on the island. 10....
  • Uncontrolled copy not subject to amendment Fundamental Principles

    Uncontrolled copy not subject to amendment Fundamental Principles

    Although the glider is normally flown by visual reference to the horizon, four flight instruments are fitted for accuracy. Three of these, the airspeed indicator, the altimeter and the turn and slip indicator function similarly to those fitted in the...
  • One-Belt-One-Road-and-Hong-Kong - Charltons

    One-Belt-One-Road-and-Hong-Kong - Charltons

    Belt and Road and Hong Kong January 2017 * * * * * * The prior approval of the Insurance Authority is required for transfer of general business from one insurer to another insurer.
  • Attendance Data 2019-2020 1 Agenda  Overview Attendance Fields

    Attendance Data 2019-2020 1 Agenda Overview Attendance Fields

    Student School Association File - Updated Definitions. Total Days Attended- The aggregate number of whole and partialdays the student attended school. If the student attended for at least a half of a day, it should be counted as a full...
  • The Life of Muhammad and the Genesis of Islam

    The Life of Muhammad and the Genesis of Islam

    The Life of Muhammad and the Genesis of Islam. Chapter 6 (part 2 of 5) Muhammad's Early Life. 570 - Born into Quraysh tribe. Father died before he was born. Raised by relatives, (uncle Abu Talib) Grandfather taught him to...
  • Literary Terms - Ms. Barath&#x27;s Classroom

    Literary Terms - Ms. Barath's Classroom

    In John Steinbeck novel "Of Mice and Men", the George killing Candy's dog foreshadows Candy killing Lennie because Candy is identical to George and Lennie to the dog. Even death of the dog was the same as Lennie's as both...
  • Creating a Mentally Healthy Workplace

    Creating a Mentally Healthy Workplace

    AGS Rehab Solutions Inc. 17 employees at head office and 300+ subcontractors and assessors across Canada . Provides disability management and assessment services to insurers, employers, lawyers and government agencies. Interest in all things mental health—30% of disability claims and...