Ted Chiang: The Problem of the Traveling Salesman

Mon 15 Dec 2008 - Filed under: Not a Journal., | Leave a Comment | Posted by: Gavin

http://lcrw.net/images/people/chiangted2.jpgThis week we’ll be highlighting some of the content in the latest issue of  LCRW which we mailed out last week.

One of the standouts is a nonfiction piece from one of the best writers we know, Ted Chiang. Ted’s fiction is absolutely brilliant. His first collection, Stories of Your Life and Others, has probably blown more minds than LSD. That may be an exaggeration, but not much. Most of the stories won awards and the title story is unspeakably heartbreaking.

“The Problem of the Traveling Salesman” isn’t heartbreaking (although it does make for a fun essay) unless you’re trying to solve the problem:

Suppose you’re a traveling salesman and you have a list of cities you need to visit. Gasoline is extremely expensive, so the problem you’re faced with is, what order should you visit the cities in to keep your fuel costs to an absolute minimum?

This is what’s known in computer science as the Traveling Salesman Problem, and while it’s easy to state, it’s actually a very difficult problem to solve. So difficult, in fact, that a really good solution would have an dramatic impact on our understanding of the nature of the universe. In this article, I’m going to try to give a brief, non-technical explanation of why this is the case.

To begin with, let’s consider the problem of sorting. When you’re playing a card game, probably the first thing you do when you’re dealt a hand is arrange the cards into order. A common way to do this is to take the card at the end and insert it next to another card so that the two of them are in order; then repeat with the card that’s at the end now, and so on until your entire hand is in order. This is a perfectly good algorithm when you have five or seven cards to deal with; you’d probably use it even if you had ten or twenty cards.

But now suppose you’re given a box containing fifty thousand index cards with words on them, and you have to sort them into alphabetical order. Now the previously described algorithm no longer seems practical. You’ll probably want to try something else; for example, you might sort the cards into piles “A–M” and “N–Z,” and then sort each of those two into smaller piles, and so on. Such a technique isn’t useful when dealing with just five or ten cards, but when dealing with fifty thousand, its advantage becomes apparent.

This is one of the most important criteria by which computer programmers judge an algorithm: how well does it deal with large numbers of items? We all expect that a task will take longer when you have more items to deal with; the question is, how much longer?

Read the rest in LCRW #23.

Comments

Leave a Reply