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.
designated arbitrarily as a "starting" city (since the solution to TSP is a Hamiltonian cycle, the choice of starting city doesn't matter).
The Held–Karp algorithm begins by calculating, for each set of cities
contains three or more cities, the number of paths through
rises quickly, but only a few such paths need to be examined to find the shortest.
The much shorter second stage adds these distances to the edge lengths
The shortest path itself (and not just its length), finally, may be reconstructed by storing alongside
the label of the second-to-last city on the path from
, raising space requirements by only a constant factor.
The Held–Karp algorithm has exponential time complexity
space to hold all computed values of the function
possible paths, each found by adding a known value of
and an edge length from the original graph; that is, it requires time proportional to
, for a total time across all subset sizes
The second stage of the algorithm, finding a complete cycle from
time and does not affect asymptotic performance.
For undirected graphs, the algorithm can be stopped early after the
This is analogous to a bidirectional search starting at
However, this is a constant factor improvement and does not affect asymptotic performance.
can be stored as a bitmask of constant multiple of machine words, rather than an explicit k-tuple.
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
reduces the algorithm's maximum space requirements, attained when
Source:[3] 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.
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.
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.