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