CODEWITHSUNDEEP
traveling-salesmanapproximationhamiltonian-cycle
Soheila DehghanZadeh
Soheila DehghanZadeh

Reputation: 419

travelling sales man for an incomplete graph

i have a large weighted graph.i want to compute an approximate shortest hamiltonian path which goes through all nodes with the lowest cost. my graph is really big that it doesn't fit in my memory. so i decided to randomly ignore some edges and load the rest in memory. but the problem is most of java TSP implementations needs a complete graph which require a huge memory in my case and i don't have that much memory. is there any java library that computes TSP on an imcpmlete graph? my staretegy was that i devided the initial vertex set into smaller parts. i computed Shorest hamiltonian path for each and then i connected all shortest hamiltonian pathes. is it a good approximation of TSP? does anyone knows a better approxiamtion algorithm of TSP for a large graph?

Upvotes: 0

Views: 1807

Answers (2)

Roland J.
Roland J.

Reputation: 86

Maybe looking at this thesis helps: https://uwspace.uwaterloo.ca/bitstream/handle/10012/4906/EmamiTaba_MahsaSadat.pdf?sequence=1 The conclusion is: "XNN is the best in terms of both tour quality and time-consumption". But the author also mentioned that "there is a lot of room to enhance the clustering and produce useful subsets of edges."

Upvotes: 0

Nuclearman
Nuclearman

Reputation: 5314

The issue is that finding Hamiltonian paths can be rather difficult as the graph gets less complete. There are a number of heuristics that may work in finding an approximate solution, such as Nearest Neighbor. Although, you run in to the chance of being unable to find a valid path.

Upvotes: 1

Related Questions