What's Up With Brute Force Algorithms?!

Ideally, when making an algorithm we want to find a way to grow the solution(s) ensuring the correct paths are taken to get to the right answer. This was seen in Dijkstra's algorithm where you want to find the shortest path from one vertex to another and the means of doing this is growing a path from the starting node and gradually learning more about the environment from visiting the other vertices. A brute force algorithm works almost in reverse: it starts off by generating all the possible solutions to the problem and then decides which ones are invalid (or which one is the best). In terms of Dijkstra's Algorithm, a brute alternative would be to generate all the possible paths from the start to the end (and we'll say no edge can be traversed twice to ensure we have a finite set of possible solutions at the end) and then scan through all the paths and calculate the total weight of them. Then the solution would be the path (or paths) with the lowest weight.

The problem with brute force algorithms is that they may require a lot of computation to generate all the possible permutations that create candidates for the solution. Looking at the graph from the blog on Dijkstra's Algorithm you can see that there are a holy-crap-that's-a-lot tonne of possible paths to take from vertex 0 to 4:

keep in mind this brute force algorithm, whilst generating the permutations, is blind to the conditions of the problem. If its job was to produce a sequence of vertices from 0 to 4, you're going to end up with 0-6 vertices inbetween. So you'll have:

0  4 //there's only one possibility with no vertices inbetween (P(6,0))

0  1  4 

0  2  4

0  3  4

0  5  4

0  6  4 

0  7  4 //there are 6 possibilities with 1 vertex inbetween (P(6,1))

0  1  2  4

0  1  3  4

0  1  5  4

0  1  6  4

0  1  7  4

0  2  1  4

0  2  3  4

0  2  5  4

0  2  6  4

0  2  7  4 

... // the amount with 2 vertices inbetween will end up being P(6,2) which is... let me see:

P(6,2) = 6!/(6-2)! = 6!/4! = 6 * 5 = 30 wow that's what I get for being lazy and thinking in terms of formulas when I could have just thought about the situation. The whole n!/(n-r)! is just another way of saying 'multiply n by (n-1) and then (n-2) and so on until you've got as many terms as there are positions for the vertices to take'. The (n-r)! just truncates the factorial to get what you want. If this isn't very clear don't worry I'll make a post on permutations and combinations soon. Anyway for now just think you've got 2 places and you've got 6 vertices to fill those places so for the first spot you have 6 to choose from and then you'll have 5 left to put in the second spot, equalling 6 * 5 = 30 permutations.

Anyway so we're going to end up with P(6,0)+P(6,1)+P(6,2)+P(6,3)+P(6,4)+P(6,5)+P(6,6) and what a good time it would be for some sigma notation:

Now 1957 doesn't seem like much (certainly not to a computer) but as you increase the number of vertices the number of permutations is going to explode (nothing grows like permutations). For example if you had 102 vertices in total which means 100 vertices that could show up between the start and end vertex, here's the number of permutations you'd get:

Have you ever had to decrease the font size in paint in order to fit a number in the frame? Because that's the level of permutational explosion we're talking about.

Now these permutations assume that the algorithm knows that the start and end vertex need to be at the start and end of the sequence in each permutation. If that restriction hadn't been imposed, the algorithm would be even more brutal (I'm using brutal here as an adjective to mean inconsiderate of the logic and restrictions of the system). There are different levels of brutality but the important fact is that the algorithm spits out all the possibilities within certain restrictions and then picks up the pieces, and the best way to improve on it is by incorporating known constraints into the permutation-generating part of the algorithm to cut down the possible solution set.

In terms of the brutal alternative to Dijkstra's Algorithm, 'picking up the pieces' refers to looking at which paths are actually possible and then deciding which path is the shortest. For determining whether a path is possible, the algorithm can go through the pairs of a given sequence much like a bubble sort, and determine whether there is an edge in the edge set, E, which contains the two vertices. If not, there's no link between them so it doesn't make sense to go directly from the first to the second vertex. So that particular sequence can get scrapped.

After a whole lot of computation, you'll be left with a set of possible solutions, where each possible solution is an actual path in the graph. Now all you have to do is go through each sequence again and compare each vertex and add the weight of their link to the total weight of that path. Then scan through the total weights and get the smallest one (like in the selection sort) and this is the solution. You could also mark the sequences which are equal to the minimum weight sequence so they can be added to the solution set (if there's multiple shortest paths) but you'll need to reset the list of minimum-length sequences as soon as you find a smaller sequence in the set. The process of finding the shortest path(s) can be done simultaneously with the process of finding which sequences aren't actually possible, but you're using a brute algorithm so clearly efficiency isn't your priority here.

So brute algorithms do a lot of number crunching when they 1) generate all the possible solutions and 2) whittle down these possible solutions to the actual solutions. These make them enormously inefficient but they get the job done (provided there are finite possible solutions), they're easy to make and for small amounts of possible states (here 1 sequence of vertices = 1 state) they aren't going to be overwhelmingly outperformed by more efficient algorithms.

I'll hopefully post a brute force solution to the famous Boat Problem soon because despite it being brute force, it's still very clever. Next up though (I've decided on it now) combinations and permutations!