Hi all
I am implementing the TSP problem in Java. Here is the question:
There are many strategies to approximate the optimal solution, amongst is the MST-Preorder-Walk strategy. Implement an algorithm that will give an approzimate solution of the TSP using this strategy. You must be able to save and represent graphically both your original (randomly generated complete, weighted, undirected) graph and the TSP route. Also provide the graphical representation of your graph at each step of the execution of the program.
And here is the MST Preorder walk strategy:
Given an undirected and weighted graph G = (Vertices,Edges,CostFunction) where |V| = n- Compute the MST using Prim's algorithm, starting at some arbitrary vertex
- List the vertices in the order they are visited in a preorder walk of the MST
- Return the Hamiltonian Cycle that visits the vertices of the graph in that order (i.e. add the edge that connects the last vertex to the "root")
- If the cost function of the graph satisfies the triangle inquality ...
c(u,w) <= c(u,v) + c(v,w) for all u,v,w in V
...then the cost of the tour found by the strategy will be a 2-approximation i.e. cost <= 2 x optimal cost
- Running time is O(n^2)
Now, I have implemented this entire program, but the problem I'm having regards the Triangle Inequality. I'm basically just having a problem interpreting what is required.
Given that the question asks for an approximate solution of the TSP problem... this approximate solution should
preferably have cost <= 2(optimal cost) ... (my general assumption)
So should I ...
a) ENSURE that the initially generated graph SATISFIES the Triangle Inequality before beginning the MST Strategy, so that the resulting TSP route WILL DEFINITELY have cost <= 2(optimal cost)?
... OR ...
b) Just randomly generate the graph, without checking for the Triangle Inequality restriction ...go on with finding the TSP route, and when it's found... THEN state whether its cost is <= 2(optimal cost) based on whether the randomly generated graph satisfies the Triangle Inequality??
Any input on this problem would be much appreciated. ... :surprised
Unsolved 
Offline 
