Brute Force Algorithmic Technique

Brute Force Algorithms - Definition & Examples
🔗
Brute force approach applied to Travelling Salesman Problem
🔗
Click here to suggest a better video
Click here to view videos suggested by visitors

Brute force technique is an algorithmic approach in which each possible variation of the input is computed until we arrive at the desired variation/combination. This approach is also called as Brute force search or Exhaustive search due to the fact that it searches each possible combination until the desired combination or the best combination is arrived at.

For example, let’s consider the problem where we need to find out if sum of any two numbers in an array/list sums up to a desired number. Assuming the array shown below is given to us and we need to find if sum of any two numbers in the array equals to 14 :

[ 1, 3, 4, 8, 6]

The brute force approach tries to enumerate all possible combinations and check if any combination gives us the desired sum of 14. Below would be all such combinations:

(1, 3) -> 4
(1, 4) -> 5
(1, 8) -> 9
(1, 6) -> 7
(3, 4) -> 7
...
(8, 6) -> 14

One other example is an algorithm to find the correct password given that the length of password can be from 8 to 16 characters. If no hints are available, the only way we can solve this is by enumerating all variations of password for each length from 8 to 16 characters and checking if the password works.

You might have already felt that this is computationally intensive. As the number of variables increase, the total number of possible combinations can exponentially increase and searching them can take a lot of time and processing power. In most of the cases, there can be some heuristics/hints which we can use to reduce the variations we create and reduce time taken by the algorithm.

References