Let’s start by looking at the number of different possible routes we could
take. Suppose there are three cities other than home, which we will label
generically as A, B, and C. There are six different available routes.
Home → A → B → C → Home
Home → A → C → B → Home
Home → B → A → C → Home
Home → B → C → A → Home
Home → C → A → B → Home
Home → C → B → A → HomeMercifully, there is a fairly easy way to see how many different routes
there are in terms of the number of cities. There are six ways to order the
three cities, as we listed above; think of 6 3 2 1. If we have to arrange
four cities, we could place any of the four cities first, and arrange the
other three in 3 2 1 ways. This gives a total of 4 3 2 1 ways of ar-
ranging four cities; mathematicians use the factorial notation 4! to abbre-
viate 4 3 2 1. T he number of ways of arranging N cities in order is N!;
the argument is basically the one used to show that four cities can be ar-
ranged in 4! different orders. So if the traveling salesman must visit N
cities, the number of different routes he could take is N!
As N gets larger, N! eventually dwarfs any positive power of N, such as
N^4 or N^10. For instance, let’s compare a few values of N! with N^4.
N N^4 N!
3 81 6
10 10,000 3,628,800
20 160,000 2.43 1018No matter what power of N we choose to compare with N!, N! always
swamps it, although when we compare N! with higher powers, such as N^10 ,
it takes higher values of N before this phenomenon starts showing up.
Greed Is Not Always Good
Nothing makes us happier than having the easy solution to a problem be-
ing the best solution; but, unfortunately, the world is so constructed that
this is rarely the case. There is an “easiest” way to construct a passable
algorithm for the traveling salesman problem; this algorithm is known as
the nearest neighbor algorithm. Whenever the salesman is in a particular
town, simply go to the nearest unvisited town (in case of ties, go in alpha-
160 How Math Explains the World