[Solved]: Solve Travelling Salesman once you know the distance of the shortest possible route

Problem Detail: 

I am trying to solve the TSP (Travelling Salesman Problem), but not in a traditional way. I am following these steps.

1) First I change the TSP to a true / false problem.

The definition of this problem is now: "Is there a route by all the cities with a total distance less or equals than k?" Let's assume I have an algorithm TSP_tf(k) to solve it.

2) Then I search the minimum k.

This is, I search "which is the distance of the shortest possible route".

An efficient algorithm to solve it would be with a dichotomic search. I begin with k=1, and I call TSP_tf(k). If it returns false, I multiply k by 2, and keep calling TSP_tf until true is returned. When this happens, search the minimum k that returns true in the interval (k/2 - k], also with a dichotomic search.

I will get then the minimum distance min_k.

3) Return the shortest route of the TSP knowing its distance is min_k.

And here is where my question comes. How would be an efficient algorithm to solve this? By efficient I mean a good approach :) It is obvious that TSP will remain being NP.

Asked By : Santiago Gil

Answered By : Santiago Gil

I managed to solve it finally.

Suppose we have a graph g which represents the cities and their conections of the TSP. A node represents a city and a weighted edge represents that there is a connection between both cities with the corresponding distance of its weigth.

In order to get the shortest route given its distance, let's delete one to one the edges, and see if they are part of the shortest route. How can we know it? If we delete an edge e from the graph and we call TSP_tf with the known shortest distance min_k, two things can happen:

• TSP_tf(min_k) == false. This is, deleting e makes not possible to obtain a route with min_k distance. e is part of the shortest route.

• TSP_tf(min_k) == true. Without the connection e, it's still possible to obtain a route with the same minimum min_k distance. e doesn't take part of the shortest route.

If we apply it progressively to all the edges of the graph, we can obtain the exact shortest route (or better said, one of the shortest routes, because there may be more than one solution).

// min_k is the distance of the shortest path of the TSP represented by the graph g. Graph TSP(Graph g, int min_k)     Graph shortestPath = g;     For (Edge e in g)         // Delete the edge e.         shortestPath -= e;         // e is part of the shortest path.         If (TSP_tf(shortestPath, min_k) == false)             shortestPath += e;         EndIf     EndFor     Return shortestPath; EndTSP 

As we know, the maximum number of nodes of a graph is $1/2 * |V| * |V-1|$, being $|V|$ the number of nodes. A TSP_tf call is done for each node, so the number of calls to TSP_tf has a peak $O(|V|^2)$, being an efficient algorithm.

Best Answer from StackOverflow

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

3.2K people like this

 Download Related Notes/Documents