CODEWITHSUNDEEP
algorithmtraveling-salesmannp
Santiago Gil
Santiago Gil

Reputation: 1302

Solve Travelling Salesman once you know the distance of the shortest possible route

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.

Upvotes: 0

Views: 1142

Answers (2)

Santiago Gil
Santiago Gil

Reputation: 1302

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.

Upvotes: 0

btilly
btilly

Reputation: 46497

Your TSP_tf is what is normally known as the decision problem version. That problem is NP-complete, see https://en.wikipedia.org/wiki/Travelling_salesman_problem#Computational_complexity for verification. Therefore you shouldn't hope that it will be very tractable.

That said, the same Wikipedia article has plenty of information on surprisingly effective ways to solve the TSP problem in practice.

Upvotes: 1

Related Questions