Solving Hard Traveling Salesman Problems
Solving Hard Traveling Salesman Problems
The task in a traveling salesman problem is to find the shortest tour through a given set of cities by visiting each city once and only once and then returning to the beginning. With this Demonstration, you can try to create a good tour, see the tour that Mathematica's built-in function FindShortestTour gives, and also see the optimal tour given by dynamic programming. The sets of cities in the Demonstration are special: The resulting traveling salesman problems are hard, so that the default method of FindShortestTour only gives a suboptimal solution.