Brute Force
A brute force algorithm is quite simple, you try everything and pick the right one. There is generally no trickery here (like with greedy), since we know we've literally tried everything.
A good exercise with any problem you come across is to first try to come up with a brute force solution, and then see if it's fast enough. Lets take Have You Driven a Fjord Lately: pdf
What might a brute force solution to this problem look like? Well, what if we try every way of allocating the m meters of bridge across the n fjords? It will be RIGHT, but is it fast enough?
well...there are about 5*10^56 integer partitions of 3000, and then about 50! = 3*10^64 ways to assign those partitions to the 50 fjords....i'm going to guess that 1.5*10^121 is probably not going to cut the mustard here, sorry.
Yes it seems silly as an exercise, but it forces you to demonstrate you know what the problem is asking, and might lend some insight. Sometimes, it's even correct, and you may not have thought about it. Consider Collision Detection pdf, which asks you to determine if any of two cars come within some range of each other. Many would start out with some parameterized line intersection nonsense....but what would a brute force solution look like? Maybe have a really small timestep and then check how far apart the cars are? How small does the timestep need to be? Well we know their maximum relative speed is 160 fps, and we need to catch them at 20 feet apart...so we need about 9 measurements a second....oh we only need to do 30 seconds of simulation? Holy cow...we can do millions of calculations a second and still be great.
So turns out brute force IS the solution here, and in particular, a certain kind of brute force that we'll call Simulation.
Recognizing Brute Force
Aside from trying it on every problem (identifying brute force using, well....brute force), there are a couple hints that a problem might be brute force
- The input size is relatively small. If you see something like, 2 cars for instance, or 11 nodes...it's a pretty good hint that it's brute force. Most brute force algorithms are exponential or factorial in runtime, so the input MUST be small for them to work
- It's an NP complete problem. You might have heard of NP complete, the classic example being the travelling salesman problem. If you recognize a problem as equivalent to one, you know it has to be brute force. Indoorienteering is a great example of this, which is literally asking for a solution to Hamiltonian Cycle which is NP complete.
Tricks
While the basic technique is simple enough, there are a few "extended" brute force techniques that come up that may push a borderline solution from too slow to fast enough
- Fix a Variable - In this technique, we choose some variable and "assume" it is correct, before possibly iterating over all values that variable can take. In the case of Indoorienteering, we fix the start point, since we know that it must be on the cycle somewhere, and we fix the halfway point (and iterate over all halfway points), because this allows us to
- Divide and Conquer - In many problems, it's possible to split the brute force up into parts that allow us to get a better runtime. In the case of Indoorienteering, we split the cycle up into two halves which gave us runtime of 2*6!, instead of 12!
Brute Force Failed
So your brute force solution is too slow, but you're pretty sure you need to try every combination to get the right answer...so what do you do next?
- What structure in the problem am I not using? (my favorite question). If brute force is too slow, but you think you HAVE to use brute force, it means your missing something about the problem. If you find what that missing structure is, it will lead you in the right direction. With the fjords problem, that structure would be that the savings aren't random, but are determined consistently by geometry...which has rules or structure that we can take advantage of, which lead us to a greedy solution.
- Where am I doing repeat work? (my second favorite question). In this case, we look at our brute force, and realize "hey, if I organize this differently, and save some small bits of work that I know are going to be the same each time, i only have to do any given bit of work once, rather than a ton of times. If you think you see a lot of repeated work, then head over to Dynamic Programming