1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Basically the same as for normal TSP. Use an LP solver and branch-and-bound for example. $\endgroup$ – adrianN Sep 29 '16 at 11:56
  • 3
    $\begingroup$ Knowing the length of the tour doesn't help. Determining if an unweighted graph has a Hamiltonian cycle is NP-complete (and you know its length if it exists). $\endgroup$ – Juho Sep 29 '16 at 12:18
  • $\begingroup$ @adrianN I think there is a better approach knowing min_k. $\endgroup$ – Santiago Gil Sep 29 '16 at 12:32
  • 4
    $\begingroup$ You're looking for an efficient algorithm to return a TSP route given the length of the optimal tour. That would be a major progress in our understanding of NP-complete problems. As such, it's far too big a request for a Stack Exchange answer. $\endgroup$ – David Richerby Sep 29 '16 at 14:48
  • 1
    $\begingroup$ "Hamiltonian cycle" is just a special case of travelling salesman, where the distance between towns is 1 if they are connected and 2 otherwise. If you can prove there is or isn't a tour of length n, then you solved "Hamiltonian cycle". $\endgroup$ – gnasher729 Sep 29 '16 at 15:57
1
$\begingroup$

You try to find a tour of length ≤ K. What would likely happen: If K is very large then a tour is easy to find. If K is very small then it is easy to prove that a tour doesn't exist. The closer you move K to the critical point (where a tour of length K exists, but K-1 doesn't exist), the harder it will be to either find a tour or prove it doesn't exist. You don't beat NP-completeness that way.

And actually, since NP-completeness is about decision problems (problems with a yes/no answer), that's what the travelling salesman problem actually is: Deciding whether or not there is a tour of length K or ≤ K.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ And what is the runtime of TSP_tf? Where are constraints encoded in your algorithm? $\endgroup$ – Evil Oct 14 '16 at 18:18
  • $\begingroup$ @Evil TSP_tf remains NP and so this implementation of TSP. Just wanted to do a reduction from TSP to TSP_tf in a polynomical number of calls (that's what I meant with efficient). What do you mean with constraints? Don't know its english meaning sorry. $\endgroup$ – Santiago Gil Oct 14 '16 at 18:23
  • 1
    $\begingroup$ I meant that it is shortest path but the requirement that it visits all places is not easily visible (hidden in TSP_tf I assume). But ok, it is clearer now what the problem was about and a bit (or rather exponentialy) easier then I understood from the first reading of the question. $\endgroup$ – Evil Oct 14 '16 at 19:43
  • 1
    $\begingroup$ By the way, NP does not stand for "non-polynomial"; it seems to me that you use it as if it did. You can look it up from e.g. Wikipedia. $\endgroup$ – Juho Oct 15 '16 at 7:12
  • $\begingroup$ Your algorithm will not return a tour if the g has more than one tour of minimum length. Some nodes would be left with more than two edges. This can be fixed. Once two edges from the same node are identified as being on the shortest path, delete all other edges connected to that node from shortest_path. If TSP_tf(shorest_path, min_k) returns true, then you are done with that node. If TSP_tf() returns false, then the two edges belong to different tours. Put all the edges back and look for another edge on that node. $\endgroup$ – Mark H Jan 28 '17 at 5:50

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.