Cheap and Secure Web Hosting Provider : See Now

[Solved]: Algorithm to use for a TSP variant

, , No Comments
Problem Detail: 

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

Asked By : user11797

Answered By : David Richerby

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).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/18589

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback