A traveling salesman must visit each of the cities 1,...,n exactly once, beginning at city 1. The distance from city i to j is cij . Write a dynamic programming recursion to minimize the distance...

A traveling salesman must visit each of the cities 1,...,n exactly once,

beginning at city 1. The distance from city i to j is cij . Write a dynamic

programming recursion to minimize the distance traveled. Hint: To preserve

the Markovian property, let the state be the set of cities visited so far. The

curse of dimensionality afflicts this problem.