Member Avatar for apcxpc

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

  • 2 Contributors
  • 2 Replies
  • 221 Views
  • 3 Days Discussion Span
  • Latest Post Latest Post by apcxpc
Member Avatar for Rashakil Fol

I'd go with interpretation b, since the third bullet says "Return the Hamiltonian Cycle ..." which means that the algorithm ends there. The fourth and fifth bullets are just informative.

Why don't you ask the person who gave you this assignment? Unless there is no such person.

Member Avatar for apcxpc

Thanks Rashakil ...I actually handed in the assignment the morning after I posted that, I ended up going with option b) after all. hehe

And also, it's sort of strange to email your lecturer with dumb questions about an assignment on Sunday afternoon, when it's due first thing Monday morning. So I figured I'd post here. :D

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.