The traveling salesperson problem (see Section 9.6) can be solved by using dynamic programming.

As an example, we solve the following traveling salesperson problem: It’s the last weekend of the 2004 election campaign, and candidate Walter Glenn is in New York City. Before election day, Walter must visit Miami, Dallas, and Chicago and then return to his New York City headquarters. Walter wants to minimize the total distance he must travel. In what order should he visit the cities? The distances in miles between the four cities are given in Table 15.