this is the recursion formula for problem :

C(i,S) = min { d(i,j) + C(j,S-{j}) }

In fact, when I tried to implement it as a code, the following code came to my mind:

int TSP(i, S){
    if(S.size == 0)
    return dist(start_vertex,i)
min = inf
cost = inf
  for(int j=0;j<S.size;j++)
      cost = dist(i,S[j])+TSP(j,S-{j});
      if(cost < min)
       min = cost;
return min;

Because this for compares n times to find the minimum, it means its recursion as:

T(n) = nT(n-1)+n ==> T(n) = O(n!)

Because each step we compare to find the minimum size of size S is, of course, the code is factorial. So what does it have to do with the subset and So why the complexity of time in the form of (n^2*2^n)? And what is the proof of its time complexity?

  • $\begingroup$ Next time I suggest taking a look at Wikipedia. $\endgroup$ Dec 12 '20 at 12:57

Your algorithm is known as the Held–Karp algorithm, and is described on Wikipedia, and also mentioned on the Wikipedia page on the traveling salesman problem.

Your implementation of the algorithm is wasteful. Using memoization, there are only at most $n2^n$ inputs. Since TSP runs in time $O(n)$ ignoring recursive calls, when using memoization, the total running time will be $O(n^22^n)$.

  • $\begingroup$ doesn't this implementation exactly correspond to the dp algorithm? So why is it factorial? $\endgroup$
    – Satar
    Dec 12 '20 at 13:55
  • $\begingroup$ Right, thanks. Your implementation doesn't use dynamic programming. $\endgroup$ Dec 12 '20 at 14:05

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.