1
$\begingroup$

The dynamic programming approach breaks the problem into $2^n n$ subproblems. Each subproblem takes $n$ time resulting in a time complexity of $\mathcal{O} (2^n n^2)$.

  • How are there $2^n n$ subproblems?

  • Why does each subproblem take $n$ time?

$n$ refers to the number of cities needed to be travelled too.

Please refer to the following pseudocode for reference: http://www.cs.berkeley.edu/~vazirani/s99cs170/notes/dynamic2.pdf

  • 0
    @FarhadYusufali: "Dynamic programming" is not an algorithm, it is a vague idea that can be used for developing algorithms in general. Are you claiming claim that there is exactly one possible way to apply this general idea to the specific Traveling Salesman Problem? If you understand the idea and the problem well enough to be sure of that, why do you need to ask anything about it?2012-09-03

2 Answers 2

3

There's a typo in the code: The loop should be over all subsets of size $s$, not $n$. The complexity is then immediate from the code and the paragraph underneath it: The two outer loops loop over the $2^{n-1}$ subsets containing $1$, and the inner loop and the $\min$ each loop over $O(n)$ cities (namely about $n/2$ on average).

2

As joriki points out there is a typo in the code: the loop should be over all subsets of size $s$ and not $n$. Looking at the initialization and the bounds for the loop we see that the total number of subproblems is $ \sum_{j=1}^{n-1} j {n-1 \choose j} = (n-1)2^{n-2} = O(n2^n)$ Each subproblem $C(S,j)$ is computing the minimum of $s-1$ numbers (each number is computed in constant time). This is clearly $O(n)$ work per subproblem.

  • 0
    Computing each of the $s-1$ numbers $C(S-\{j\},i)+d_{ij}$ takes constant time per number. Finding the minimum of these $s-1$ numbers involves $s-2$ comparisons (simply scan the list of values while keeping track of the smallest number found). Since $s \leq n$ this require $O(n)$ time.2012-09-03