0
$\begingroup$

Time complexity of travelling salesman problem is $O(n^2*2^n)$ using held-karp algorithm. Now, if don't use dynamic programming and solve it using the recursive procedure, time complexity is still $O(n^2*2^n)$. I know there are overlapping of subproblems and there will be less computations but the time complexity is not getting better with the use of dynamic programming. Moreover, space complexity using held-karp is also $O(n*2^n)$ which is very large. We mostly use dynamic programming when we can improve the time complexity.

So, should we use dynamic programming here?

Here is the recursive approach..

TSP(graph, start, target) {
  if start == target {
    return 0;
  }

  min = infinity;
  for neighbor in neighbors(graph, start, target) {
    tour_length = TSP(remove(graph, start), neighbor, target)
                  + distance(graph, start, neighbor);
    if tour_length < min {
      min = tour_length;
    }
  }
  return min;
}
$\endgroup$
1
$\begingroup$

Time complexity using the recursive method is trying all "reachable" permutations of nodes before getting back to the first node which is in worst case $n!$ (if all permutations are reachable).

However using recursion with memory may reduce it to the complexity of the DP solution. But using memory in itself is the idea behind the DP solution.

$\endgroup$

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.