Complexity of Held–Karp algorithm for TSP

The computing procedure:

\(C(\{1\},\ 1) = 0\)

for \(s = 2\) to \(n\) :

for all subsets \(S\subseteq \{1,2,...,n\}\) of size  \(s\) and containing \(1\) :

\(C(S, 1) = \infty\)

for all \(j\in S\) , \(j \neq 1\) :

\(C(S,j) = min\{C(S-\{j\},i) + d_{ij} : i\in S, i\neq j)\}\)

return \(min_{j,\ j\neq 1} C(\{1,2,...,n\}, j) + d_{j1}\)

Complexity:

\(\sum_{s=2}^{n}\binom{n-1}{s-1} \cdot (s-1) \cdot (s-1) + (n-1)\) , where for a specific \(s\) ,

\(\binom{n-1}{s-1}\) is the number of possible subset \(S\) ;

the first \((s-1)\) represents the number of possible \(j\) to consider;

the second \((s-1)\) means for each \(j\) , to get the \(C(S,j)\) , we have to consider \(s-1\) possible \(i\) .

\((n-1)\) is for the last returning statement.

By transformation:

\(\sum_{s=2}^{n}\binom{n-1}{s-1} \cdot (s-1) \cdot (s-1)\)

\(=\sum_{2}^{n}\frac{(n-1)!}{(n-s)!(s-2)!} \cdot (s-1)\)

\(=\sum_{2}^{n}[\frac{(n-1)!}{(n-s)!(s-3)!} + \frac{(n-1)!}{(n-s)!(s-2)!} ]\)

\(=\sum_{2}^{n}[(n-1)(n-2)\binom{n-3}{s-3} + (n-1)\binom{n-2}{s-2}]\)

The complexity is \(O(n^2 2^n)\) . Note that \((n-1)!\approx \sqrt{2\pi (n-1)} (\frac{n-1}{e})^{n-1}\) . It is much larger than  \(O(n^2 2^n)\) .

Refer to:

  1. Held–Karp algorithm
  2. Stirling's approximation

文章归档

阅读更多

Be First to Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注