dynamic programming for TSP

general
1

Hi I interest in the algorithm for standard TSP in O(n^2*2^n) solution using dynamic programming, but i don’t find nothing really serious.Please if somebody gime a link to a explanation of this algorithm.Thanks

2

I assume that TSP stands for Traveling Salesman Problem. I didn’t understand the complexicity you are looking for. Is it

O(O(n^{22^n}))

or

O({n^22}^n)

but in fact it doesn’t really matter, both this numbers are greater than n^n and this is greater than n!, and n! is number of permutation, so you can check all possibilities and it will be quicker.

3

Man n! is check all possibilities in TSP, of course this is essential, but exist an algorithm named Held–Karp algorithm that solves the problem in time O(n^2*2^n).I need real documentation about this.

4

You can see that single character can be important, there was O(n^22^n) in your original post (propabably because star was removed by the forum)