The Brute Force Algorithm
Only 435,236,889 combinations to go!
Pick a number between 1 and 10.
Got it?
Okay, your number is 3.
Did I get it right? No? I have 9 other tries.
Okay is it…5? No? Okay is it…4? No?
Is it 8? (just change your answer to 8 if it wasn’t already at this point).
It was 8?! Wow, I cannot believe I got that right!
Using the brute force algorithm, I was able to get the right answer. It took a few tries but I eventually got it right.
This algorithm’s main purpose is to search every possible choice (no matter how long it takes) until it picks the correct one.
However, what if I gave you a padlock with 5 numbers. You don’t know the combination, so now you have to test an insane amount of different combinations to see which one is the right one. That would take an exhausting amount of time and energy.
Let’s say the correct combination was 52897. We need to search for 52897 (k) in the 99,999 (n) other number combinations (since there are 5 numbers in the combination, there would be 10⁵ or 100,000 number combinations in total) until we find the right combination.
That might be the reason why this problem’s time complexity is O(n*k). Thanks brute force algorithm…
There’s a known brute force algorithm in computer science. It’s called the traveling salesman problem (or TSP for short). It’s like this:
You are given a list of cities and the cost of traveling between each city. You need to find out which path will allow the traveling salesman to visit each city once, starting and ending in the same city, and spending the least amount of money traveling. Each city is like a point on a map, and the salesman travels between each one once and ends in the city he started with.
Turns out, there is a current 2020 solution found for this problem for 48 states in the United States:
If you want to travel to one city in each of the 48 states that is the most cost effective, you would follow this map. Pretty cool right?
Here’s a graph that shows the same approach but with more numbers and arrows:
In the graph above, you would have to find a combination between each letter to see which path is the least distance, and visits each letter once.
The brute force algorithm might not be the most time efficient, but it serves as a simple algorithm to follow (and always works no matter how many tries!).
If you want more information on brute force problems and TSPs, check out Hamiltonian paths.
Sources:
Brute Force Algorithms Explained. (2020, January 6). freeCodeCamp. Retrieved April 4, 2023, from https://www.freecodecamp.org/news/brute-force-algorithms-explained/
Cornell University. (n.d.). Traveling salesman problem. https://optimization.cbe.cornell.edu/index.php?title=Traveling_salesman_problem
Hamiltonian path. (2023, February 19). In Wikipedia. https://en.wikipedia.org/wiki/Hamiltonian_path
Hamilton Paths and Hamilton Circuits. (n.d.). Retrieved April 4, 2023, from https://intranet.missouriwestern.edu/cas/wp-content/uploads/sites/17/2020/05/Hamilton-Paths-and-Hamilton-Circuits-1.pdf
Most Important Type of Algorithms. (2023, March 28). Coding Ninjas. Retrieved April 4, 2023, from https://www.codingninjas.com/codestudio/library/types-of-algorithms-and-their-uses
Travelling Salesman Problem. (n.d.). Tutorials Point. Retrieved April 4, 2023, from https://www.tutorialspoint.com/design_and_analysis_of_algorithms/design_and_analysis_of_algorithms_travelling_salesman_problem.htm#:~:text=A%20traveler%20needs%20to%20visit,returns%20to%20the%20origin%20city%3F
