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.
