What is Brute-force search?
Brute-force search is a general problem-solving technique and algorithmic paradigm that involves generating a list of all the possible candidates for a solution and then testing the validity of every single candidate. It is also known as exhaustive search or generate and test. It involves systematically enumerating all possible candidates for the solution and checking whether each candidate satisfies the problem's statement. Brute-force search is the most common search algorithm because it does not need any domain knowledge. However, it can take a lot of run time and could be rather inefficient.
Essentially, in brute-force search, you have to iterate through all the candidates, checking whether they satisfy the problem’s statement. You check each candidate till you find the right one. So, if the candidate that satisfies the problem statement is at the end of the collection, you’ll have to check all the candidates in the collection. It’s even possible that the candidate may not exist in the collection, in which case you’d still end up checking every single candidate in the collection, but to no avail.
If the solution exists in the collection, you will be able to find it with brute-force search, however, the costs involved in this technique are proportional to the number of candidate solutions.
In the real world, for a lot of problems, the number of candidates is far too high (Combinatorial explosion). Because of this phenomenon, the brute-force method is applied when problem-specific heuristics can be applied to reduce the number of candidate solutions available to a size that is manageable.
What are brute-force algorithms?
Brute-force algorithms rely purely on sheer computing power to find solutions for problems. They try every single solution that could possibly solve the problem instead of employing advanced techniques to get the job done in a more efficient manner.
Some of the features of brute force algorithms are:
- A brute force algorithm is an intuitive, direct, and straightforward technique of problem solving that enumerates all the possible ways or all the possible solutions to a specified problem.
- Several problems that arise in day-to-day life are solved through the use of the brute force strategy, for example exploring all the paths to a nearby park to find the minimum shortest path, or arranging the books in a rack using all the possibilities to optimize the rack spaces, etc.
- Even though optimal algorithms are also possible, a lot of daily life activities use a brute force nature.
How can you speed up brute-force searches?
One of the ways in which you can speed up a brute-force algorithm is by reducing the search space (reducing the set of candidate solutions) by making use of heuristics that are specific to the problem class.
As an example, in the eight queens problem the challenge, the challenge involves placing eight queens on a standard chessboard so that no queen attacks any other queen. Due to the fact that each of the queens can be placed in any of the 64 squares, in principle there are 648 = 281,474,976,710,656 possibilities to consider. However, since all the queens are alike, and no two queens can be placed on the same square, the candidates are all possible ways of choosing of a set of 8 squares from the set of 64 squares. Which means 64 choose 8 = 64!/(56!*8!) = 4,426,165,368 candidate solutions – about 1/60,000 of the previous estimate. In addition to this, no arrangement that features two queens on the same row or the same column can be an acceptable solution. Because of this, you can further restrict the set of candidates to those arrangements.
This example demonstrates that a small amount of analysis would quite often lead to very significant reductions in the number of candidate solutions, and could potentially turn an intractable problem into a trivial one.
In some situations, the analysis could reduce the candidates to the set of all valid solutions. This means that it could yield an algorithm that directly enumerates all the desired solutions (or finds one solution, as appropriate), without wasting time on tests and the generation of invalid candidates. As an example, for the problem "find all integers between 1 and 1,000,000 that are evenly divisible by 417" a naive brute-force solution would generate all integers in the range and test every single one of them for divisibility. However, that problem can be solved with a far greater degree of efficiency by starting with 417 and repeatedly adding 417 until the number exceeds 1,000,000 – which takes only 2398 (= 1,000,000 ÷ 417) steps, and does not require any tests.
What are the advantages of the brute-force search?
The advantages of the brute-force search are:
- If all the possible solutions are listed down, then you can be guaranteed that the brute-force approach will find the correct solution.
- It is applicable to problems that exist in a very wide range of domains.
- It is useful for solving small and simple problems.
- It is very simple, does not require any domain knowledge, and can be used as a comparison benchmark.
What are the disadvantages of the brute-force search?
Here are the disadvantages of brute-force search:
- The brute-force method is very inefficient. For real-time problems, algorithm analysis quite frequently goes above the O(N!) order of growth.
- Finding the right solution by this method consumes a lot of time. These algorithms run rather slowly.
- Instead of using a good algorithm design, these algorithms just rely on compromising the power of the computer.
- These algorithms are neither constructive nor creative in comparison to algorithms that are constructed through the use of some other design paradigms.
