How to solve the traveling salesman problem without checking every single possible route

How to solve the traveling salesman problem without checking every single possible route
Image: Intellect (generated)

In short: The traveling salesman problem asks for the shortest path visiting every city exactly once. Brute-force searches are impossibly slow, but the Held-Karp algorithm offers a smarter way. By using dynamic programming to store intermediate results, it finds the exact solution in exponential time rather than the much slower superexponential pace.

Proposed independently by Bellman, Held, and Karp in 1962, the Held-Karp algorithm provides a systematic method to solve the traveling salesman problem (TSP). The core challenge of TSP is finding a minimum-length Hamiltonian cycle—a tour that visits every city exactly once before returning to the start. Because the cycle is closed, the choice of the initial city is arbitrary, allowing the algorithm to designate one as a fixed starting point.

The algorithm functions through dynamic programming, breaking the problem into smaller, manageable subproblems. It calculates the shortest path for subsets of cities, storing these results to avoid redundant computations. When evaluating a path to a new city, the algorithm examines the shortest paths to all possible second-to-last cities within a subset. By adding the known distance of these shorter paths to the final edge length, it identifies the optimal route for that specific subset. This process continues until the algorithm has computed paths that visit every city.

While the Held-Karp algorithm is significantly more efficient than brute-force methods, it remains computationally demanding. It operates in exponential time and requires substantial memory to store the computed values for all possible subsets of cities. Despite these space requirements, which grow by a constant factor, it remains a foundational technique for solving TSP and related challenges like the Hamiltonian cycle problem. By focusing on only a few necessary paths rather than every permutation, it transforms an intractable search into a structured, albeit still complex, calculation.

Opens the Intellect+ feed with this card first. Swipe up for the next one.

Sources

To cite this card, link to https://intellectplus.co.uk/app/science-held-karp-algorithm.

How we source, check and correct cards: Editorial standards.

General information, not professional advice. Spotted an error? Flag the card or see corrections and complaints.

Intellect Plus is a visual educational discovery platform for exploring fascinating facts and ideas. Brain Food, Not Brain Rot. What is Intellect Plus?

Related

Finding something worth knowing…