Euclidean TSP with backtracking. Modify your program from Exercise 5.5.43 to stop the search for any path that is longer than the length of the current known minimum tour. Print a table showing the number of possibilities tried in the two cases for various n, using random points with positive integer coordinates less than 1 million.
Exercise 5.5.43
Euclidean TSP. Develop a Java program TSP that tries all possibilities to find a minimal-length TSP tour (see Exercise 5.5.12). Use a recursive program that maintains an array marking all the cities on the current path and tries all possibilities for the next city. Note: Your program will not finish for large n, because there are (n−1)! / 2 different possibilities to try, and n! is far, far larger than 2n (see Exercise 5.5.1). No one knows an algorithm that can guarantee to solve this problem for large n.
Exercise 5.5.12
Consider the following classic problem:
Traveling salesperson (TSP). Given a set of n cities and a distance m, find a tour through all the cities of length less than or equal to m, or report that no such tour exists.
To avoid technical problems with comparing sums of square roots of integers, assume that all distances are integers (say, the Euclidean distance in miles or in meters, rounded to the nearest integer). Prove that TSP is in NP by developing a polynomial-time check() method that checks whether a given tour is a solution to a given instance. Assume that the arguments to check() are an integer n (number of cities), an integer m (desired tour length upper bound), two integer arrays x[] and y[] (x-and y-coordinates of the points), and an integer array tour[] that specifying the order in which the cities appear on the tour.
Exercise 5.5.1
Fill in the blanks in this table (to within a factor of 10 for large numbers).