The Held–Karp algorithm, also called Bellman–Held–Karp algorithm, is a
dynamic programming
Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics.
I ...
algorithm proposed in 1962 independently by
Bellman and by Held and
Karp
Karp may refer to:
Places
* Karp, Podlaskie Voivodeship, in north-east Poland
* Karp, Lublin Voivodeship, in east Poland
People
* Karp (surname)
* Karp Khachvankyan (1923–1998), Armenian actor and director
Other uses
* KARP-FM, a radio st ...
to solve the
traveling salesman problem
The travelling salesman problem (also called the travelling salesperson problem or TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each cit ...
(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 the mathematical field of graph theory the Hamiltonian path problem and the Hamiltonian cycle problem are problems of determining whether a Hamiltonian path (a path in an undirected or directed graph that visits each vertex exactly once) or a ...
, in
exponential time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
.
Algorithm description and motivation
Number the cities
, with
designated arbitrarily as a "starting" city (since the solution to TSP is a cycle, the choice of starting city doesn't matter). The Held–Karp algorithm begins by calculating, for each set of cities
and every city
not contained in
, the shortest one-way path from
to
that passes through every city in
in some order (but not through any other cities). Denote this distance
, and write
for the length of the direct edge from
to
. We'll compute values of
starting with the smallest sets
and finishing with the largest.
When
has two or fewer elements, then calculating
requires looking at one or two possible shortest paths. For example,
is simply
, and
is just the length of
. Likewise,
is the length of either
or
, whichever is shorter.
Once
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. For instance, if
is shorter than
, then
must be shorter than
, and the length of
is not a possible value of
. Similarly, if the shortest path from
through
to
is
, and the shortest path from
through
to
ends with the edge
, then the whole path from
to
must be
, and not any of the other five paths created by visiting
in a different order.
More generally, suppose
is a set of
cities. For every integer
, write
for the set created by removing
from
. Then if the shortest path from
through
to
has
as its second-to-last city, then removing the final edge from this path must give the shortest path from
to
through
. This means there are only
possible shortest paths from
to
through
, one for each possible second-to-last city
with length
, and
.
This stage of the algorithm finishes when
is known for every integer
, giving the shortest distance from city
to city
that passes through every other city. The much shorter second stage adds these distances to the edge lengths
to give
possible shortest cycles, and then finds the shortest.
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
to
through
, raising space requirements by only a constant factor.
Algorithmic complexity
The Held–Karp algorithm has exponential time complexity
, significantly better than the superexponential performance
of a brute-force algorithm. Held–Karp, however, requires
space to hold all computed values of the function
, while brute force needs only
space to store the graph itself.
Time
Computing one value of
for a
-element subset
of
requires finding the shortest of
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
. There are
-element subsets of
; and each subset gives
possible values of
. Computing all values of
where
thus requires time
, for a total time across all subset sizes
. The second stage of the algorithm, finding a complete cycle from
candidates, takes
time and does not affect asymptotic performance.
For
undirected graph
In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...
s, the algorithm can be stopped early after the
step, and finding the minimum
for every
, where
is the
complement set
In set theory, the complement of a set , often denoted by (or ), is the set of elements not in .
When all sets in the universe, i.e. all sets under consideration, are considered to be members of a given set , the absolute complement of is t ...
of
. This is analogous to a
bidirectional search
Bidirectional search is a graph search algorithm that finds a shortest path from an initial vertex to a goal vertex in a directed graph. It runs two simultaneous searches: one forward from the initial state, and one backward from the goal, stopping ...
starting at
and meeting at midpoint
. However, this is a constant factor improvement and does not affect asymptotic performance.
Space
Storing all values of
for subsets of size
requires keeping
values. A complete table of values of
thus requires space
. This assumes that
is sufficiently small enough such that
can be stored as a
bitmask
In computer science, a mask or bitmask is data that is used for bitwise operations, particularly in a bit field. Using a mask, multiple bits in a byte, nibble, word, etc. can be set either on or off, or inverted from on to off (or vice versa) in ...
of constant multiple of
machine word
In computing, a word is the natural unit of data used by a particular processor design. A word is a fixed-sized datum handled as a unit by the instruction set or the hardware of the processor. The number of bits or digits in a word (the ''word s ...
s, 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
for a
of size
requires only values of
for subsets of size
. Keeping only the