We have seen that we can solve one type of integer programming (the knapsack problem) with dynamic programming. Let's try another.

The traveling salesperson problem is to visit a number of cities in the minimum distance. For instance, a politician begins in New York and has to visit Miami, Dallas, and Chicago before returning to New York. How can she minimize the distance traveled? The distances are as in Table 5.

The real problem in solving this is to define the stages, states,
and decisions. One natural choice is to let stage *t* represent
visiting *t* cities, and let the decision be where to go
next. That leaves us with states. Imagine we chose the city we are
in to be the state. We could not make the decision where to go next,
for we do not know where we have gone before. Instead, the state has
to include information about all the cities visited, plus the city we
ended up in. So a state is represented by a pair (*i*,*S*) where *S* is
the set of *t* cities already visited and *i* is the last city
visited (so *i* must be in *S*). This turns out to be enough to get a
recursion.

The stage 3 calculations are

You can continue with these calculations. One important aspect of
this problem is the so called *curse of dimensionality*. The
state space here is so large that it becomes impossible to solve even
moderate size problems. For instance, suppose there are 20 cities.
The number of states in the 10th stage is more than a million. For 30
cities, the number of states in the 15th stage is more than a billion.
And for 100 cities, the number of states at the 50th stage is more
than 5,000,000,000,000,000,000,000,000,000,000. This is not the sort
of problem that will go away as computers get better.

Sun Jun 14 13:05:46 EDT 1998