The Travelling Salesman Problem

You are a salesman and you must visit 20 cities spread across North America. You must visit each city once and only once. The question is this: In what order should you visit them to minimize the total distance that you have to travel?

The answer is that there is no simple answer. Reasonable people will make a reasonable choice and accept a reasonably short path.

However there is only one way to find the absolute shortest path, and that is to write down every possible ordering of cities, compute the distance for each of those orderings, and pick the shortest one.

How many orderings are there? They can be counted this way:
  • For the first city to visit you have 20 choices.
  • For the second city to visit you then have only 19 choices (because you can't visit the first city again).
  • For the third city you have 18 choices,
  • and so on . . .
  • For the last city you have 1 choice
These numbers must be multiplied together to give the total number of orderings:

= 2,432,902,008,176,640,000 possible orderings
This number is so big that if your computer could check 1 million orderings every second it would still take 77,000 years to check them all! Thus even though we know how to solve the Travelling Salesman Problem we still can't do it.

The Factorial (!) Notation:

To write down a positive integer like 20 followed by an exclamation mark means to multiply all the numbers from 1 to 20 together.

We say it like this: "twenty factorial".

Look for the factorial function on your calculator. Here are more examples:
  • 2! = (2)(1) = 2
  • 5! = (5)(4)(3)(2)(1) = 120
  • 69!=1.71x1098 (the biggest number my calculator can display)



Click here to return to the Math Entertainment page.