Computer Science

Computer Science RSS

Traveling Salesman Problem ... question about Triangle Inequality

Please support our Computer Science advertiser: Learn about neural networks and artificial intelligence.

•

Join Date: Sep 2004

Posts: 55

Reputation: apcxpc is an unknown quantity at this point

Solved Threads: 0

apcxpc

Offline

Junior Poster in Training

Traveling Salesman Problem ... question about Triangle Inequality

Oct 30th, 2005

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

•

Join Date: Jun 2005

Posts: 2,047

Reputation: Rashakil Fol is just really nice

Solved Threads: 139

Rashakil Fol Rashakil Fol is offline

Offline

Super Senior Demiposter

Re: Traveling Salesman Problem ... question about Triangle Inequality

Nov 2nd, 2005

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.

All my posts may be redistributed under the GNU Free Documentation License.

•

Join Date: Sep 2004

Posts: 55

Reputation: apcxpc is an unknown quantity at this point

Solved Threads: 0

apcxpc

Offline

Junior Poster in Training

Re: Traveling Salesman Problem ... question about Triangle Inequality

Nov 3rd, 2005

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.