Now for non-geeks, what does the cartoon in part one mean? When thinking about finding the optimal solution to a problem, one question is how “hard” is the problem. If there are only two solutions, then you could probably spend the time to evaluate both and pick the better one. Most problems have many solutions, and so any algorithm to find the best is going to have to evaluate some number of potential solutions in order to find the best.
This leads to the “order” notation, O(n). What this says is the problem is “order n” and that while we might not know the exact time to evaluate each possible solution, we know we are going to have to check about “n” of them.
Now the traveling salesman problem (TSP) is one where we have to visit some number of locations, one after the other. Suppose I sell golf balls and want to visit five different golf courses today. I start at my house, and I go to one of the golf courses. From there I can choose one of the remaining four. From there, I choose one of the three, and so on, until I return home at the end of the day. How many different ways are there to do this? Turns out that this is the number of permutations of the five (and if you count your home, actually six) locations, and the number of permutations is given by n! = n(n-1)(n-2)…(2)(1). One way to solve the problem is to check every solution, all n! of them.
Suppose there are 10 locations to visit, and that your laptop computer can figure out the length of a trip with a certain visiting sequence in one thousandth of a second. You can come back to your computer in about an hour for the solution. What happens if you add two locations to visit. The awful truth about factorials is they grow like crazy, and now your computer needs five days to find the solution. What to solve 15 locations? It will take your computer 40 years. Ouch.
So geeks try to find sneaky ways to evaluate all the “good” solutions, and implicitly check the others without doing any work. Dynamic programming is one of the sneaky methods for evaluating only some of the possible solutions, but still knowing that the best of the ones you find is better than all of the possible n! solutions. The algorithm in the cartoon is O(n^2 x 2^n). So for 10 locations, we can solve the problem in about one second (instead of an hour). Twelve locations takes four seconds, and 15 takes about a minute. Much better than 40 years!
So geeks win? Not so fast. Try thirty locations — 12 days. Thirty-five locations? A year. Forty locations? 35 years. Don’t even think about 100 locations…
What does O(1) mean? The third panel guy can sell to 100 golf courses by doing just one thing. Okay, you need to have a particularly warped sense of humor to find that funny. But such senses of humor do exist (me, unfortunately).
If you’ve read this far, thanks. But is this problem really important? Do salesmen really do this? Well think about oil delivery trucks or a beer distributor who restocks convenience stores. Lots of locations, lots of choices about who to visit today, and who to visit tomorrow, and the price of gas for your truck keeps going up.
Or think about making printed circuit boards. A robot arm (usually) picks the chips from a storage position (sometimes attached to a tape) and puts them on the board in a particular location. The optimal sequence (the shortest trip to visit the n chip sites on the board) may take a lot less time than a non-optimal one, increasing costs and reducing capacity. Could there be 100 chips on a board? Sure.