The Held–Karp algorithm, also called the Bellman–Held–Karp algorithm, is a dynamic programming algorithm proposed in 1962 independently by Bellman[1] and by Held and Karp[2] to solve the traveling salesman problem (TSP), in which the input is a distance matrix between a set of cities, and the goal is to find a minimum-length tour that visits each city exactly once before returning to the starting point. It finds the exact solution to this problem, and to several related problems including the Hamiltonian cycle problem, in exponential time.
Number the cities
1,2,\ldots,n
1
S\subseteq\{2,\ldots,n\}
e ≠ 1
S
1
e
S
g(S,e)
d(u,v)
u
v
g(S,e)
S
When
S
g(S,e)
g(\emptyset,e)
d(1,e)
g(\{2\},3)
1 → 2 → 3
g(\{2,3\},4)
1 → 2 → 3 → 4
1 → 3 → 2 → 4
Once
S
S
1 → 2 → 3 → 4
1 → 3 → 2 → 4
1 → 2 → 3 → 4 → 5
1 → 3 → 2 → 4 → 5
1 → 3 → 2 → 4 → 5
g(\{2,3,4\},5)
1
\{2,3,4\}
5
1 → 4 → 3 → 2 → 5
1
\{2,3,4,5\}
6
5 → 6
1
6
1 → 4 → 3 → 2 → 5 → 6
\{2,3,4\}
More generally, suppose
S=\{s1,\ldots,sk\}
k
1\leqi\leqk
Si=S\setminus\{si\}=\{s1,\ldots,si-1,si+1,\ldots,sk\}
si
S
1
S
e
si
1
si
Si
k
1
e
S
si
g(Si,si)+d(si,e)
g(S,e)=min1g(Si,si)+d(si,e)
This stage of the algorithm finishes when
g(\{2,\ldots,i-1,i+1,\ldots,n\},i)
2\leqi\leqn
1
i
d(i,1)
n-1
The shortest path itself (and not just its length), finally, may be reconstructed by storing alongside
g(S,e)
1
e
S
The Held–Karp algorithm has exponential time complexity
\Theta(2nn2)
\Theta(n!)
\Theta(n2n)
g(S,e)
\Theta(n2)
Computing one value of
g(S,e)
k
S
\{2,\ldots,n\}
k
g
k
k
\{2,\ldots,n\}
n-k-1
e
g(S,e)
|S|=k
n-1
\Theta(n)
For undirected graphs, the algorithm can be stopped early after the step, and finding the minimum for every , where is the complement set of . This is analogous to a bidirectional search starting at and meeting at midpoint . However, this is a constant factor improvement and does not affect asymptotic performance.
Storing all values of
g(S,e)
k
g(S,e)
If only the length of the shortest cycle is needed, not the cycle itself, then space complexity can be improved somewhat by noting that calculating
g(S,e)
S
k
g
k-1
g(S,e)
S
k-1
k
\Theta(\sqrt{n}2n)
Source:[3]
function algorithm TSP (G, n) is for k := 2 to n do g(k) := d(1, k) end for for s := 2 to n−1 do for all S ⊆, |S| = s do for all k ∈ S do g(S, k) := minm≠k,m∈S [g(S\{k}, m) + d(m, k)] end for end for end for opt := mink≠1 [g({2, 3, ..., n}, k) + d(k, 1)] return (opt) end function
Besides Dynamic Programming, Linear programming and Branch and bound are design patterns also used for exact solutions to the TSP. Linear programming applies the cutting plane method in integer programming, i.e. solving the LP formed by two constraints in the model and then seeking the cutting plane by adding inequality constraints to gradually converge at an optimal solution. When people apply this method to find a cutting plane, they often depend on experience, so this method is seldom used as a general method.
The term branch and bound was first used in 1963 in a paper published by Little et al. on the TSP, describing a technique of combining smaller search spaces and establishing lower bounds to enlarge the practical range of application for an exact solution. The technique is useful for expanding the number of cities able to be considered computationally, but still breaks down in large-scale data sets.
It controls the searching process through applying restrictive boundaries, allowing a search for the optimal solution branch from the space state tree to find an optimal solution as quickly as possible. The pivotal component of this algorithm is the selection of the restrictive boundary. Different restrictive boundaries may form different branch-bound algorithms.
As the application of precise algorithm to solve problem is very limited, we often use approximate algorithm or heuristic algorithm. The result of the algorithm can be assessed by C / C* ≤ ε . C is the total travelling distance generated from approximate algorithm; C* is the optimal travelling distance; ε is the upper limit for the ratio of the total travelling distance of approximate solution to optimal solution under the worst condition. The value of ε >1.0. The more it closes to 1.0, the better the algorithm is. These algorithms include: Interpolation algorithm, Nearest neighbour algorithm, Clark & Wright algorithm, Double spanning tree algorithm, Christofides algorithm, Hybrid algorithm, Probabilistic algorithm (such as Simulated annealing).