I’m a traveling man, don’t tie me down

While I was waiting for a shuttle the other day (Microsoft has a fleet of shuttle busses that take people all over the campuses) I was thinking about optimization heuristics.

Often we want to find an algorithm that determines the best way to do something. For example, the traveling salesman problem: given a set of cities and the cost of driving between all of them, what is the cheapest route that visits every city at least once? Such problems can be extremely difficult to solve! But often we miss out on the fact that we don't need to find the optimal solution, we need to find the "good enough" solution. Or we need to find a solution that has bounded inoptimality. Often finding the best solution is impractical, but it would be nice to know that you can find a solution that doesn't suck too bad.

For the traveling salesman problem, for instance, you can easily construct the minimum spanning tree of the graph. Then the route becomes trivial: pick any node as the root, do a depth-first traversal of the spanning tree and go back to the root. You'll visit every edge twice and end up where you started from. The total cost is twice the cost of traversing the spanning tree once, and obviously the cost of the optimal solution can't possibly be better than the cost of traversing the minimum spanning tree once.

This doesn't give you an optimal solution (unless your graph is already a tree, of course) but it does give you a solution that is guaranteed to be between 100% and 200% of the optimal solution, and that might be good enough.

This sort of 200% heuristic crops up all the time. Do you rent DVDs or buy them? Suppose a DVD costs $24 to buy and $6 to rent. Obviously the optimal solution is to buy it if you are going to watch it four or more times, rent otherwise -- but that requires perfect knowledge of the future.

Can we come up with an algorithm that minimizes the maximum suckiness, given no information about the future? Well, the worst possible situation is buying a DVD and watching it once -- you just overpaid by a factor of four. Actually, no, a worse situation still is renting the DVD so many times that you end up paying way more than the purchase price.

The solution? Rent the DVD the first four times, and then the fifth time, buy it. No matter how many times you watch it, the worst you can do is pay 200% of the optimal price and typically you'll do a lot better. (Particularly if you can bring to bear more information, such as being able to forecast the number of future viewings.)

This same heuristic applies to waiting for shuttles, which is why I was thinking about this in the first place. How long should you wait before you give up and walk? If the shuttle is going to be right there 30 seconds after you call, it's foolish to walk. But it is also foolish to wait ten times as long as it would have taken you to walk.

I waited as long as it would have taken me to walk, and then I walked. Fortunately it was a nice day yesterday.

Comments (6)

  1. Eric Lippert says:

    Hmm, come to think of it, it would be better to buy the DVD on the fourth viewing. Then the worst case is 4 viewings for $42, which is less than twice the optimal case. But whatever, you take my point I’m sure.

    Don’t forget people, my degree is in MATHEMATICS, not ARITHMETIC.

  2. You can always sell a dvd on ebay. Also, you can read while waiting for the shuttle. And you can also read on the shuttle.

  3. Eric Lippert says:

    Indeed. In fact, I’ve taken to doing crossword puzzles. I can usually do the entire USATODAY crossword puzzle in one shuttle trip, but USATODAY publishes pretty unchallenging puzzles.

  4. Bruce says:

    Another good trick is to pre-calculate when possible. If the program is always calculating the postman’s path for the same set of cities, you’re better off just calculating the ideal path once in advance, and hard-coding that knowledge in your program.

  5. Ben Wilhelm says:

    The only problem with precalculating is that if your data changes, you have to remember to precalculate it again. I write games for the PS2, and we’d be doomed without some form of precalculation . . . but on the minus side, rebuilding a level takes anywhere from an hour to a day to get it in full working order again.

    Luckily it’s all automated – in fact, we can rebuild the entire game with two commands if we want – but it’s just a bit slow.

  6. Alan Dean says:

    It seems to me that the solution is a probabilistic algorithm. Each time you view a film, you gain more knowledge as to the probability of watching the film more than once. This explains the behaviour of buying classic movies from the past without having watched the DVD version.
    If you watch a film once, the probability of watching becomes more known than before you watched it. For example, if the film was dross you may think "the chances of me watching that film again are nil! Heck, if it comes on I’m leaving the room."
    When you make it probabilistic, other behaviours start to make more sense too – why do we ask our friends and peers what they think of a new release? Because we can factor in the extent to which those who share our tastes enjoyed a film to our decision to view.
    As an aside, I think that this is the driver behind the Amazon "people who bought this also bought" feature set.

Skip to main content