TOPICS
Search

Held-Karp Algorithm

The Held-Karp algorithm is a dynamic programming algorithm for finding a minimum-weight Hamiltonian cycle, and therefore an exact solution of the traveling salesman problem. Let the vertices of a complete weighted graph be 1, 2, ..., n, let c_(ij) be the weight of the graph edge joining i and j, and fix vertex 1 as the starting point. For a nonempty subset S subset= {2,...,n} and j in S, define D(S,j) to be the minimum weight of a path that starts at 1, visits precisely the vertices in S, and ends at j.

For j=2,...,n, the initial values are

D({j},j)=c_(1j).
(1)

For |S|>=2, the recurrence relation is

D(S,j)=min_(i in S\{j})[D(S\{j},i)+c_(ij)].
(2)

The minimum tour length is then

L=min_(j in {2,...,n})[D({2,...,n},j)+c_(j1)].
(3)

Evaluating the subsets in increasing order of size gives O(n2^n) states, each of which examines at most n possible preceding vertices. The resulting running time is O(n^22^n), and storing the full table and one minimizing predecessor per state requires O(n2^n) space. Following the predecessors reconstructs a minimum tour. Bellman (1962) published a closely related dynamic programming treatment of the traveling salesman problem.

See also

Dynamic Programming, Hamiltonian Cycle, Traveling Salesman Problem

Explore with Wolfram|Alpha

References

Bellman, R. "Dynamic Programming Treatment of the Travelling Salesman Problem." J. Assoc. Comput. Mach. 9, 61-63, 1962. https://doi.org/10.1145/321105.321111.Held, M. and Karp, R. M. "A Dynamic Programming Approach to Sequencing Problems." J. Soc. Indust. Appl. Math. 10, 196-210, 1962. https://doi.org/10.1137/0110015.

Cite this as:

Weisstein, Eric W. "Held-Karp Algorithm." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Held-KarpAlgorithm.html

Subject classifications