CIT 594 Assignment 10: Travelling Salesman
Spring 2011, David Matuszek

Purposes of this assignment

General idea of the assignment

“Solve” the Travelling Salesman problem.

In this instantiation of the problem, a salesman wants to visit each of the 50 U.S. state capitals, then return to his starting point. He wants to cover the minimum total distance (also called the cost) when doing so. No city can be visited more than once. Plan his route.

The word “solve” is in quotation marks because you won’t be able to find the optimum route. This is because there are 50! possible paths (actually 49!, since the path is a cycle, and any city can be used as the starting point.) With problems of this type, we can easily find ways to reduce the number of permutations to consider, but these reductions still result in an algorithm that is essentially O(n!).

The putative goal of this program is to find the best possible route (if you get under 18000 miles, you are doing well), but the real goal is to make a Thread-safe program to do it.

Details

I am providing the following:

You should make a travellingSalesman package, containing:

Notes

Shared state will result in errors if:

To encourage such errors to occur, I need a method that is so  s l o w  that it is likely to be interrupted. This is harder than it sounds, because each Thread can execute thousands or millions of instructions between interruptions. In this assignment, SolutionSaverAndChecker.run() is an appropriately slow method: it loops through the sharedCityArray, printing each City to an unbuffered PrintStream, and accumulating information about that City as it goes. By the time it finishes printing, the data in sharedCityArray may have changed. Do not speed this method up, or give it a copy of the shared array. Instead, use synchronization to solve the problem.


The basic job of a Worker thread is: Rearrange cities until you find a better ordering, then compare it to the ordering in sharedCityArray. Copy the better ordering into the less good one, then do it all over again.

How do you find a better ordering? For this assignment, I recommend using a random number generator, and making random small changes in the ordering until you happen to find a better ordering. There is plenty of time to try a few million orderings. If you want to explore the extensive literature on the Travelling Salesman problem, that’s okay too, so long as your Worker threads aren’t all doing the same work.

Sample output

Here's a portion of output from my program. Your output should provide the same kind of information.

 0  Montgomery, Alabama       [32.3615, -86.2791]
 1  Juneau, Alaska            [58.3019, -134.4197]
 2  Phoenix, Arizona          [33.4485, -112.0738]
 ...
48  Madison, Wisconsin        [43.0747, -89.3844]
49  Cheyenne, Wyoming         [41.1455, -104.8020]

Total distance = 58803.517735751055

Worker 1 found a better distance on trial 2:  57415.875153771
Worker 1 found a better distance on trial 12:  57388.76286745295
Worker 1 found a better distance on trial 13:  57184.80580373073
...
Worker 6 found a better distance on trial 49:  50580.94449533747
ERROR! Cities have been duplicated or omitted!
Expected city sum = 1225
Actual city sum   = 1312
Difference        = 87
ERROR! Reported distance is 47275.212601280495 but actual distance is 53330.7747242515!
Worker 6 found a better distance on trial 51:  50520.923362174195
...

All done!

 8  Tallahassee, Florida      [30.4518, -84.2728]
 ...
17  Baton Rouge, Louisiana    [30.4581, -91.1402]
Total distance = 23559.759298308334

Due date

Turn your assignment in to Blackboard before 6AM Wednesday, April 20.