In this problem, we consider the use of simulated annealing for solving the traveling-salesman problem (TSP). You are given the following:
• N cities;
• the distance between each pair of cities, d;
• a tour represented by a closed path visiting each city once, and only once.
The objective is to find a tour (i.e., permutation of the order in which the cities are visited) that is of minimal total length L. In this problem, the different possible tours are the configurations, and the total length of a tour is the cost function to be minimized.
(a) Devise an iterative method of generating valid configurations.
(b) The total length of a tour is defined by
where P denotes a permutation with P(N + 1) = P(1). Correspondingly, the partition function is
where T is a control parameter. Set up a simulated-annealing algorithm for the TSP.