CODEWITHSUNDEEP
c++algorithmvisual-c++
Ananth Saran
Ananth Saran

Reputation: 207

Clustering algorithm for a TSP

I am trying to solve a very large TSP with about 10,000 cities. To parallelize my task, I want to divide these cities into clusters and solve the TSP for each cluster.

I want a way in which i can seperate my cities into clusters ( on the basis of density of cities/ proximity between each city in that cluster).

Does anyone know an efficient order to do this?

Upvotes: 1

Views: 1451

Answers (2)

Sephra
Sephra

Reputation: 23

There are several density-based clustering algorithms that are just the tool you're looking for, for separating points into clusters anyway.

DBSCAN is the main one from which the others are derived. OPTICS is a extension of DBSCAN that doesn't produce clusterings per se, but makes a plot of points that you can inspect to extract clusters (there's another part of the algorithm that automatically extracts clusters as well.) DBSCAN is simpler, OPTICS is more flexible. Both of these get better with an appropriate indexing structure such as R-tree. There are implementations in toolkits such as ELKI, scikit, and WEKA.

(and, as j_random_hacker says, there's no guarantee of global optimality for the TSP by doing it this way)

Upvotes: 0

Drakosha
Drakosha

Reputation: 12165

There's a simple approximation algorithm which promises the solution is at most 2 times worst than the optimal solution (at least in the Euclidean metric if i remember correctly). The algorithm is: get a minimal spanning tree. Use tree edges to travel.

I'd research for better approximation algorithms instead of inventing one yourself.

To separate to clusters, if you want to do it, there's K-means and other algorithms (in the same article)

Upvotes: 5

Related Questions