Homework 10

Details

Implement an algorithm in Algoraph to solve the Traveling Salesperson problem. Your goal is to get the exact answer if possible, but otherwise get the best answer you can in a reasonable amount of time. So you might have multiple algorithms: an exact one and an approximation one.

Start as follows:

In Eclipse, create a new Algoraph Algorithm. Use WeightedInstance as the data type.
To be sure you have the latest plugin, right after you create the new algorithm, right-click on the project and select "Update Algoraph.jar from Algoraph".
On the first line of the runAlgorithm method, put the following line of code:
```
int[][] A = puzzle.getAdjacencyMatrix();
```
(If this gives a compiler error, the jarfile is not up to date.) This will allow you to use the weighted adjacency matrix A in your algorithm and ignore the rest of the method calls and awkward ways of accessing the edge weights.

The algorithm should return a string that gives the cost of the optimal cycle followed by a ":" and then followed by the order the vertices should be visited with spaces between the vertices.

For instance, a valid output for a vertex with 6 vertices might be: 34:0 1 4 3 5 2.

Note: A valid solution on a graph with n vertices will be a permutation of the numbers 0 through n-1.
Grades will be based on how many of the following graphs your algorithm can correctly solve and how close you can come to the optimal solution on the rest (the puzzleID for each is given in parentheses):

K05 TSP (1325)
K09 TSP (1319)
K10 TSP (1320)
K12 TSP (1321)
K15 TSP (1322)
K20 TSP (1323)
K25 TSP (1324)
K30 TSP (1326)
K35 TSP (1327)
K40 TSP (1328)
K45 TSP (1329)
K50 TSP (1330)

Algoraph has a few classes that you might find helpful in the package cusack.hcg.graph.algorithm.util. Unfortunately, they are not well documented. But here they are, listed in the order of the most likely you might want to the least likely:

PermutationGenerator allows you to iterate over all of the permutations of the set {0,1,2,...,n-1}. It has methods next() and hashNext() like a typical iterator does.
KSubsetGenerator allows you to iterate over all k-subsets of the set {01,1,2,...,n-1}.
KPermutationGenerator allows you to iterate over all k-permutations of length k from the set {01,1,2,...,n-1}. So if n=5 and k=3, it would generate 012, 013, 014, 023, 024, 034, 123, 124, etc.

Get the test program TSPTests.java from the AlgorithmTests page. You can cut-and-paste the code from there into a new class in Eclipse. It is a JUnit test so you can run it easily. You will need to rename the type of variable from TSP to whatever the name of your algorithm class is in 2 places on line 88. If you don't want it to run them all (because some of them are large and might take years to run) you can comment out the line that says @Test before any test you do not wish it to run. This program will run your code and give you an indication of whether or not it worked properly, but it cannot always tell you if your answer is correct (since I don't know the optimal solution for some of them). If you look at the test cases, for the small ones the answer is known (the tests that call a 2-argument verifyStuff method). For the rest, I have indicated in a comment a bound on the optimal solution based on previous students' solutions (and just the ones I happened upon. It is possible another student did better but I can't find a record of it right now.)

Submit your algorithm and a file called results.txt that gives the solution to each graph using Webhandin 385-HW10. Each line of results.txt should contain the name of the graph followed by a colon followed by the output of your algorithm (which should be in the format described above).

Finally, bring a write-up to class that describes the algorithm(s) you tried. Explain why you choose the algorithm(s) you did and describe how they performed--both in terms of speed and in terms of optimality of the solutions obtained. Then discuss ideas for improving your algorithm(s).