Simplification of the Traveling Salesman Problem

Question

I'm not sure I can call it a simplification of TSP but here it is:

Suppose you're given the Traveling Salesman Problem but in addition, you're also given the shortest possible distance (not the route) for the whole journey. How much faster would it be to find the shortest possible route with this extra bit of information?

$\\$

Note: I realize that the answer depends on what algorithm you choose. So you feel free to use your favourite algorithm to make this comparison.

Answer 1

In the worst case, it is as difficult as the original problem without the hint. For example, suppose that all weights are $1$, and I tell you that the shortest tour has length $n$, where $n$ is the number of nodes.

Answer 2

Suppose that your original algorithm had complexity $O(N)$. Like, the brute force method requires $N=n!$ with $n$ the number of destinations. Then depending on at which of your checks you find the minimum, it could be the 1st, 2nd, third check, ..., all the way to the last one. On average, you will need $\frac{1+2+...+n!}{n!}=\frac{n!(n!+1)}{2n!}=\frac{n!+1}{2}$. So I say that the complexity in the brute force method is still on the order of $O(n!)$.

If you're using something like branch and bound algorithm, let's use an example where you have 5 cities to visit total and you start with the first one and must return back to the first one. Let the distance between cities be given by the matrix

A="
5 4 3 2 11
4 6 10 3 5
3 10 3 2 3
2 3 2 8 3
11 5 3 3 11"

Without knowledge of the shortest path, you need 54 cycles through the branch and bound algorithm.

With knowledge of the shortest path, which is length 16, the algorithm for this particular problem finds the best route after 13 cycles. In general, you should be able to stop as soon as you come upon the length of the route matching the shortest route. You might also be able to make some improvements in "pruning" branches.