1
$\begingroup$

What type of algorithm would you suggest me to use for this problem? I want to implement an algorithm that minimize the total distance in a graph (TSP) but for only X nodes. Also, we can go as many times we want on every vertices and/or edges. Let's say, on my graph, that I want the minimum distance for visiting every blue node. What algorithm and heuristic would you recommand me? An approximation running in reasonable time would be acceptable.

For this example, this is an undirected graph, the vertices are points in the plane and the cost of an edge is the distance between its endpoints.

graph

$\endgroup$
  • $\begingroup$ If the edges have no directions, the graph is called "undirected". Still, finding an optimal TSP route/cycle in an undirected graph embedded in the euclidean plane is NP-hard. I don't know good approximation algorithms for that, but I would google "TSP undirected euclidean approximation" or something along those lines. $\endgroup$ – G. Bach Dec 4 '13 at 0:14
2
$\begingroup$

The minimum weight connected subgraph that includes all the blue vertices is known to be a tree, called a Steiner tree. A depth-first search of the tree will give you a route that visits every blue vertex and whose length is twice the weight of the Steiner tree, since you walk along each edge of it exactly twice. Hence, DFS of a Steiner tree is at most twice the length of the shortest route.

However, computing Steiner trees of general weighted graphs is NP-hard (the decision version was one of Karp's 21 problems). Sanjeev Arora has shown there's a polynomial time approximation scheme for the the Euclidean version of the problem, which is close to the case you're interested in: paper. The Euclidean version corresponds to your version where every possible edge is present (i.e., you have a collection of points in the Euclidean plane and there's an edge between every pair of points, with the weight of the edge equal to the distance).

$\endgroup$
  • $\begingroup$ I think I found something GREAT, what do you think of this algo : umcs.maine.edu/~markov/SteinerTrees.pdf $\endgroup$ – user11797 Dec 4 '13 at 1:04
  • $\begingroup$ @user11797 Looks good. That would give you an answer to your problem guaranteed to be within a factor of 4 of the optimum. $\endgroup$ – David Richerby Dec 4 '13 at 9:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.