Brute force approaches aim to find a satisfactory solution to a problem by exploring all possible solutions. As a result of brute force, all possibilities are explored until a satisfactory solution cannot be found.
Such an algorithm can be of two types:
- In this case, the best solution is found by optimizing. Depending on the value of the best solution, finding the best solution may either involve finding all the possible solutions or stopping when it has found the best solution. An example would be finding the best path for the traveling salesman problem. Traveling all the cities and keeping the cost of travel as low as possible is the best path here.
- Once a satisfactory solution is found, it stops finding the solution. An example would be finding a traveling salesman path that is within 10% of optimal.
- Brute force algorithms often take exponentially long to run. The following heuristics and optimizations can be used:
- You can use a heuristic to determine which possibilities to look at first based on a rule of thumb.
- The elimination of certain possibilities without exploring all of them is called optimization.
- A brute force search considers every state of a tree, represented as a node. As far as the starting position is concerned, we have two choices, i.e., A state and B state. We can either generate state A or state B. In the case of B state, we have two states, i.e., state E and F.
- A brute force search considers each state individually. According to the above tree, brute force search takes 12 steps to find the solution.
- In contrast, backtracking, which uses Depth-First search, considers the below states only when they provide a feasible solution. Consider the above tree, start from the root node, then move to node A and then node C. Consider states G and H only if node C provides a feasible solution. Backtracking from node C to node A. Next, we move to node D. Since node D does not provide a feasible solution, we backtrack from node D to node A.
- From node B, we move to node E. Since node K is a solution, finding it takes 10 steps. As a result, we are able to eliminate a greater number of states in a single iteration. As a result, backtracking is faster and more efficient than brute force.
- Advantages of a brute-force algorithm
The following are the advantages of the brute-force algorithm:
- Moreover, it is guaranteed to find the correct solution to a problem by finding all the possible solutions.
- There are many applications for this type of algorithm.
- Smaller and simpler problems are usually solved with it.
- It is a benchmark for solving a simple problem and does not require any particular domain knowledge.
- Disadvantages of a brute-force algorithm
Brute-force algorithms have the following disadvantages:
- Due to the fact that each state must be solved individually, it is an inefficient algorithm.
- Because it solves each state without considering feasibility, it is a very slow algorithm to find the correct solution.
- Compared to other algorithms, brute force is neither constructive nor creative.
Lets start implementation
// An example univariate function.
val f: UnivariateRealFunction = object : AbstractUnivariateRealFunction() {
override fun evaluate(x: Double): Double {
return (x - 1) * (x - 1)
}
}
// Optimizes a univariate function using Brute Force Search method.
val solver = BruteForceMinimizer(
1e-15, // epsilon
20) // max number of iterations
val soln = solver.solve(f)
val xmin: Double = soln.minimizer()
val fmin: Double = f.evaluate(xmin)
println(String.format("f(%f) = %f", xmin, fmin))