The dumbest way to be smart

In Dutch we say “He who is not strong, must be smart”. Today I’d like to talk about the converse of that proverb. He who is not smart must be strong, or at the least be willing to work incredibly hard. You see, CS and by extension AI, is about being smart and efficient in a lazy way. Most methods are about a way to avoid having to do work. And that is a good idea. As you’ll see today’s post on brute force methods, being dumb can be a way of being smart. Of you’re willing to work for it, that is.

Honest-to-god-bare-bones brute force is rarely used anymore nowadays, even though we have more computing power than ever. This is largely due to the widespread use of libraries that include optimised and debugged implementation of almost every algorithm you could think of. It used to be the case that if you wanted to find something using something fancy as A* you had to do it yourself, but I’d be surprised if there was anyone who’s implemented quicksort themselves outside of a CS class since the 1990s. It is, however, still useful to study it a bit in detail, due to its general applicableness, and since it forms a good baseline to compare other algorithms too.

A peek under the hood

As you probably have guessed from the name, brute force is not very subtle. It boils down to, “try every possible combination and see what works best”. The first step in this algorithm is to find all possible actions, which is usually harder than it sounds. After that, we make a copy of the data we are working with to manipulate. Using the copied data we will then perform one of the steps and repeat the process until we reach a terminal state. We then decide whether this terminal state is what we want and work our way back from there. After our search is done we discard the copied data and return our solution.

How does it work in practice?

I can talk about it in the abstract all day long, but it will be clearer if I just show you some examples:

Example (Closest pair problem): A common problem is to find the two points in a set that are closest to each other. Formally this is formulated as follows: Given n points p_1,p_2,\ldots,p_n in space find p_i,p_j such that d(p_i,p_j) is minimal among these points. Using the brute force approach means creating a list of all possible pairs of points, computing their distance and then finding the minimum of that list.

Suppose we have n points to consider. That means that the list will contain \frac12n(n-1) items. That might not sound like a lot but think about it. If we try it with just 10 points we have to generate and check a list of 45 items. By the time we’re up to just 100 points that a list of 4950 items! Here it is also important to note that as we increase the dimension of our points finding the distance also becomes more and more work. For example, in statistics, it is not uncommon to ask this question about points in 10 or even 100-dimensional space.

Example (Traveling Salesman problem): The travelling salesman problem (TSP) is a famously hard problem. The problem is as follows: Given a graph find the shortest path starting and ending in the same place visiting each of the nodes exactly once. In laymen’s terms, this is like finding the shortest route in a list of cities, visiting every city exactly once and returning home at the end. In this case, the brute force approach is to first generate all possible paths, then calculate their length and then find the minimal amongst those.

Again suppose that you have n cities to consider. We now have to consider \frac12(n-1)! paths! Just to give you a sense of how much that is, if we consider a list of just 10 cities that gives us 181 440 routes to consider. By the time we’re up to 15 cities we have to consider 43 589 145 600 routes!

Downsides

There is a lot to be said about the problems above, which is all outside the scope of this post. They are just there to give you an idea how quickly things can get out of hand if you try this approach. By now you might be thinking that brute force is useless in almost any situation, but sometimes it is all you have. There are a lot of problems out there for which there simply is no other known solution. While it is true that for some problems brute force in unfeasible for all but the smallest cases, it’s all about finding the right tool for the job.  If it’s the only thing available, that makes the choice pretty easy.  If you don’t expect to have to handle big data sets it might be worth to try it.

Silver linings

One of the biggest advantages brute force has is the ease of implementation. There are no leaky abstractions or subtleties that you have to get exactly right for it to work. Provided you have a way to enumerate all possible actions to consider you can just leverage all the computing power you have. After the previous examples, this approach might seem terribly naive, but it’s not impossible to use this algorithm and get acceptable results. If you have a little development time and the load is relatively small this can still provide a “good enough” solution. It can also work together in conjunctions with other methods. There are pruning techniques you can apply to limit the size of the possibility space you have to search. If you still haven’t found the solution after you did, you can still use brute force.

Another advantage brute force has is that it can actually make use of all the computing power you have. Problems like this usually don’t require a lot of access to the available data. Because of that, this approach is often very well parallelizable. So if you have a lot of computing power at your disposal, this can actually leverage all of that. This happens less often than you would like.

Obviously, this isn’t the most complicated algorithm out there, but I hope I have given you an idea about how it works, and what limitations it has. I hope it can provide a stepping stone to understanding other algorithms, so you don’t have to be the dumb kind of smart yourself.

Like, Share, subscribe:
RSS
Facebook
LinkedIn
Google+
http://modernwizardry.xyz/dumbest-way-to-be-smart/