Algorithms for finding a shortest closed route that visits every city once, the classic traveling salesman problem. The Held-Karp algorithm solves it exactly by dynamic programming in exponential time, which is far faster than trying every route, while Christofides' algorithm gives a tour guaranteed to be within a fixed factor of the best possible one for distances that obey the triangle inequality.
All Traveling Salesman Tour Algorithms
Filter Results2 entries
Sources
Wikipedia: Held-Karp algorithm
Has Member: Held-Karp Algorithm, LeadQuote, Has Member: Held-Karp Algorithm, Lead
The Held-Karp algorithm, also called the Bellman-Held-Karp algorithm, is a dynamic programming algorithm proposed in 1962 independently by Bellman and by Held and Karp 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.
Christofides Algorithm (Wikipedia)
Has Member: Christofides Algorithm, LeadQuote, Has Member: Christofides Algorithm, Lead
The Christofides algorithm or Christofides-Serdyukov algorithm is an algorithm for finding approximate solutions to the travelling salesman problem, on instances where the distances form a metric space (they are symmetric and obey the triangle inequality).
Reader 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.