Held–Karp Traveling Salesman

The Traveling Salesman Problem (TSP) asks for the shortest possible route that visits each city exactly once and returns to the origin city. The Held-Karp algorithm uses dynamic programming to solve TSP exactly in O(n² 2ⁿ) time, which is much faster than the O(n!) brute-force search.

Experiment

You can interactively explore different instances:

1. Open the Held-Karp module.
2. Observe the optimal tour and cost for the default Square instance.
3. Change the Instance to Asymmetric. Notice how the distances depend on the direction.
4. Change to Disconnected to see what happens when no Hamiltonian tour is possible. The cost will be Unavailable.