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