This homework asks you to implement a recursive
algorithm that uses "search with backtracking" to compute
an optimal solution to the *travelling salesman problem (TSP)*.
You will use ideas similar to those used to solve the *n queens* problem (see
Queens.java).
You will test your implementation on the set of 128 cities given in miles.dat.
This homework is an important part of Project 2.

The *travelling salesman problem (TSP)* takes as input a set of cities and pairwise distances
between these cities and outputs a shortest tour that visits every city exactly once and
returns to the starting city.
The basic "search with backtracking" algorithm for this problem is quite simple.
Suppose we have somehow computed a tour `T`, representing our current best solution to the problem.
We would now like to systematically generate all possible tours, rejecting long (i.e., bad) tours as quickly as
possible.
Specifically, as soon as we have a partial tour whose length is longer than the length of `T`,
we should reject that tour immediately and move on to generating the next tour.
On the other hand if we have completed the generation of a tour, say `R`, then that must
mean that `R` is shorter than `T`, and therefore we replace `T` by
`R`.
When I say "partial tour" I mean a tour that starts at a city, visits a
few cities (not necessarily, all) exactly once and returns to the starting
city.
Here is the pseudocode for a function called `TSP` that expresses this algorithmic idea.

// R is a partial tour; initially, it may be empty or just contain the first city // T is the current best tour; it may be computed greedily, initially void TSP(R, T) { // Base case: we have discovered a tour better than T if (R is a complete tour) { T <- R; return; } // Another base case: our partial tour is not worth completing if (R is longer than T) { delete the last city from R; return; } // Recursive case: R is not complete and is currently better than T // and is therefore worth completing for (each city c not in R) do { append c to R; TSP(R, T); } // end of for-loop } // end of TSP

The use of the "current best" tour `T` to prune our search is critical and is our only hope that
we can compute a traveling saleman tour of 128 cities in a reasonable amount of time.
Notice that as the algorithm proceeds, `T` gets shorter and this may lead to quicker pruning later.
Initially, `T` can be computed *greedily*.
One version of a greedy algorithm is the following. Suppose we have a partial tour, say `P`.
Consider each city `c` not in `P` and consider all ways of inserting `c`
between a pair of adjacent cities in `P`.
The *cost of inserting c* is the smallest increase in the cost of
`P` by inserting `c` between any pair of adjacent cities.
The best city to add to `P` in this greedy
step is the city with smallest cost of inserting.
The partial tour `P` grows in this manner until it becomes a complete tour.
To get the greedy algorithm started, you can pick the shortest triangle (i.e., a tour with
3 cities) as `P`.

Even though the pseudocode is given, there are a number of implementation decisions to be made.
How are the tours going to be represented (a `String[]`, an `int[]`, or
maybe a doubly linked list)?
Does the function `TSP` need additional arguments that will make it easier to
check base case conditions?
What should the return type of `TSP` be (is it ok to leave it `void`)?
Think carefully about these choices; not all choices are equal and some can make your life
quite complicated.

You can break up what you have to do for this homework into 3 main steps:

- Read the names of cities and their pairwise distances from miles.dat. Recall that you have already done this for Project 1. You may use the code I posted, if you wish. Note that only the array containing the names of the cities and the 2-d array containing pairwise distances between cities is relevant to this homework.
- Implement a method called
`greedyTSP`that uses the greedy algorithm described above to compute a traveling salesman tour (which may not be optimal). - Implement the
`TSP`method using the pseudocode described above.

Recall that the data file miles.dat contains a list of 128 cities
and their pairwise distances.
The number of permutations of 128 cities is roughly 3 followed by 215 zeros!
This is an incredibly large number - e.g., larger than the number of atoms in the universe.
So unless our algorithms prunes most possible tours, there is no way we can solve TSP
for 128 cities.
Even with pruning, it is quite likely that we cannot solve TSP on 128 cities quickly enough.
So make sure that you first
test your implementation on smaller sets of cities. For example, you
can take the first 20 cities in miles.dat to see if your program
can compute a solution to TSP with 20 cities.
In addition to `TSPTester.java`, submit a file called `TSPTester.pdf` that
answers the following questions:

- How long does your program take to solve TSP of 5, 10, 15, 20, 25, ..., 100, 125, 128 cities? It is quite possible that your program is unable to solve TSP for more than a few cities; state clearly the largest problem size that your program was able to handle.
- Can you think of any other ways in which we can substantially speedup the solution of a TSP?