Travelling Salesman

Discover the shortest route for visiting a group of cities

Visualization by Nishchay Garg

The Problem

A traveling salesman is getting ready for a big sales tour. Starting at his hometown, suitcase in hand, he will conduct a journey in which each of his target cities is visited exactly once before he returns home. What is the best order in which to visit them, so as to minimize the overall distance traveled?

The Visualization

• Click anywhere in the space to mark the positions of the cities.
• The total number of cities can be in the range [3,15].
• Press the play button to discover the optimum path.

The Best Part

No general method of solution is known.

Credits

Algorithm : Held-Karp Algorithm (DP)

Presentation Graphics  : https://www.behance.net/thelittlewonder