CIS 554 Clojure Assignment 3: Traveling Salesman

Fall 2013, David Matuszek

- To teach STM (Software Transactional Memory) in Clojure

You probably know the Traveling Salesman problem. A salesman wants to visit each of N cities exactly once, then return to his starting point, and to cover the minimum possible distance while doing so. Your assignment is to write a program to find an approximate solution to this problem, using STM.

There are more efficient ways to tackle this problem. Don't worry about that; just program the algorithm described below.

Here is a file containing the latitudes and longitudes of the capitol cities of each of the 50 US states. You can read this in from a file, or build it directly into your Clojure program.

Below is some Java code for computing the distance between two points on Earth, which you should convert to Clojure.

```
/**
* Computes the distance between two locations on Earth.
*
* @param lat1degrees Latitude, in degrees, of the first location.
* @param long1degrees Longitude, in degrees, of the first location.
* @param lat2degrees Latitude, in degrees, of the second location.
* @param long2degrees Longitude, in degrees, of the second location.
* @return The distance, in miles, between the two locations.
*/
private static double distance(double lat1degrees, double long1degrees,
double lat2degrees, double long2degrees) {
final double earthRadius = 3956; // miles
double lat1 = toRadians(lat1degrees);
double long1 = toRadians(long1degrees);
double lat2 = toRadians(lat2degrees);
double long2 = toRadians(long2degrees);
double dLat = lat2 - lat1;
double dLong = long2 - long1;
double sinHalfLat = sin(dLat / 2);
double sinHalfLong = sin(dLong / 2);
double a = square(sinHalfLat) + cos(lat1) * cos(lat2) * square(sinHalfLong);
double c = 2 * atan2(sqrt(a), sqrt(1 - a));
return earthRadius * c;
}
private static double square(double x) {
return x * x;
}
```

The initial path will be the sequence of capitol cities, in order. Determine the cost of this path. Use this path and its cost as the *current best solution*.

Whenever an improvement to this path is found, save the new path, the cost of the path, and the id of the agent that found it. Print the agent number and the new cost, for example `Agent 3 found a path with cost 213097.8626953470357.`

Create 100 agents, numbered 1 to 100, giving each agent a copy of the current best solution.

Each agent should:

- Make a small change, or a small number of changes, in the current best solution to try to find a better solution.
- Don't have each agent trying the exact same changes as every other agent! You can avoid this by using some randomness in your approach, or by using the agent's number in some way.

- If the agent's new solution is better than the "official" current best solution,
- Replace the current best solution, and
- Continue trying to improve this solution.

- If the new solution is worse that the current best solution,
- Discard this agent's new solution,
- Get a new copy of the "official" current best solution,
- Try to improve that solution.

Stop the program when 1000 improvements have been made. Print the final path.

Your program is due before **6am Wednesday, October 9,** via Canvas.