Coping with intractability: the Travelling Salesman Problem

In the Travelling Salesman Problem, our goal is to visit each capitol city in the 48 contiguous states exactly once, except for the starting city which we must return to at the end. Continuing from the lab, we'll start by trying to solve the method via brute force. To do so, we'll iterate over all the Hamiltonian cycles and recording the cycle with the lowest summed cost. Since this takes basically the same time as the time to calculate the Hamiltonian Cycles, this method has no hope of finishing in a reasonable amount of time. Since we want to get a relatively decent result, we're going to try to get an approximately good solution.

Tasks

  1. Calculate the brute force solution

    Create a method to find the shortest hamiltonian cycle. This method will not have a good runtime, but it will at least give the 'right' answer.

    public static List<Graph.Edge<V, E>> minTSP(Graph<V, E> g, Graph.Vertex<V, E> source): returns the minimum distance Hamiltonian cycle. I recommend using your allHamCycles method from the lab and just iterating through the result.

    If you try to run this method on the 48 states, you'll quickly find that it has no hopes of finishing anytime soon. So, we'll need to try something else.

  2. Find the Minimum Spanning Tree

    A similar but distinct graph problem is to calculate the minimum spanning tree. A minimum spanning tree of a graph is the collection of edges of minimal combined weight that connects all the vertices.

    public static Collection<Graph.Edge<V, E>> mst(Graph<V, E> g): this method finds a minimum spanning tree in the given graph and returns it as a collection of edges. I recommend using Prim's algorithm, but you are free to implement it however you want.

  3. Use the MST of the states graph to get an approximate solution

    Since the brute force calculation of the Travelling Salesman Problem takes too long, lets use our MST to get an approximate solution. Specifically, we'll just use depth first search over the edges of our graph to do so. One thing you might find super helpful for this method: I made a constructor in the Graph class that takes a collection of edges and builds a graph out of them. So you can take your MST that you find and use that constructor to build the graph using only those edges, which will make it much easier to perform a depth first search from any particular vertex.

    I goofed. When I made this, I was thinking to myself: "oh, they want to just do DFS over the edges of the MST and use that to make a cycle, so if I gave them a constructor that built a graph only using the edges for the MST that would be super useful - gosh I'm so nice". But this was dumb; since we need Hamiltonian cycles, we need to not repeat vertices, which means we need to use 'short-cut' edges which are not contained in the MST. Hence a graph containing only the edges of the MST would be completely useless for us. That being said, the method itself doesn't really change too much - you still want to get the MST of the graph, pick a starting vertex, then use the edges of the MST to determine what the allowed neighbors are of each vertex, and perform a DFS using those edges.

    public static <V, E> List<Graph.Edge<V, E>> tspApprox(Graph<V, E> g): using the supplied graph, computes a minimum spanning tree, then performs a depth first search over that to compute a Hamiltonian cycle.

    This approximation actually turns out to be 2-approximation: the cost of this solution is at most twice the cost of the optimal solution. Not bad!

Explorations

Try changing the way your methods work: specifically, I imagine that your methods currently are deterministic (that is, they run the same way every single time). This has drastic effects on various things: try adding randomness to the order in which you proceed in your depth first search in the tspApprox method and see how it changes the performance.

Extensions

The following are some suggested extensions. You should feel free to pursue your own custom extensions to your project that you find interesting. Please clearly identify your extensions in your report. In your code, make sure the baseline simulations run properly. Making a separate sub-folder for major extensions is recommended.

  1. Do better! Do your best to find the shortest hamiltonian cycle and write about the methods you chose. Are these methods only applicable to the 48 states, or can they be adapated to general graphs?
  2. Use other (reasonably large) datasets and see how your algorithms perform.
  3. Implement other cool graph algorithms! Connectivity, Network flow, Finding Negative Cycles, etc.

Report

Your intended audience for your report are your peers not in the class, but who have taken a CS course. Your report should explain the core CS concept used, present the results of your program, and discuss the meaning of the results: what did you discover and does it make sense?

Your project report should contain the following elements. Please include a header for each section.