The Held-Karp algorithm solves the travelling salesman problem exactly using dynamic programming, computing the shortest path that visits every subset of cities ending at each possible city, building up from small subsets to the full set of cities so each larger subproblem reuses previously computed smaller ones. It runs in O(n squared times 2 to the power n) time, exponential but a substantial improvement over the O(n factorial) time of brute force enumeration of all possible routes. Michael Held and Richard Karp published the algorithm in 1962, and it remains the standard method for computing exact travelling salesman solutions on modestly sized instances.
Facts
Classification
Design Technique Credited ToMichael Held and Richard Karp (1962), independently Richard Bellman 1 Connections
Invented By
Richard Karp co-developed this dynamic programming algorithm for the traveling salesman problem with Michael Held, published in 1962.
Source Wikipedia: Richard M. Karp
Sources
1. Wikipedia: Held-Karp algorithm
Lead section, history
proposed in 1962 independently by Bellman and by Held and Karp
entity record, description (design-technique)
The Held-Karp algorithm solves the travelling salesman problem exactly using dynamic programming, computing the shortest path that visits every subset of cities ending at each possible city, building up from small subsets to the full set of cities so each larger subproblem reuses previously computed smaller ones.
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.