Traveling Salesman Game
Attention gamers! You are a traveling salesman. Your task: visit the cities (represented as dots on the gameboard) one by one by clicking them. Start anywhere you like. You will trace out a route as you proceed. You must visit every city once and then return to your starting point. The goal is to find the shortest possible route that accomplishes this. Your total distance is recorded at the bottom of the panel, along with the total distance of the best route that Mathematica can find.[more]
Note that Mathematica will not always be able to find the best possible route, so it is conceivable that you will be able to find a shorter route than Mathematica's best. While this is not likely, especially when there are only a small number of cities, if you play enough (and are skillful) you will eventually encounter this phenomenon.
Tips for game play: The scoreboard will reset when the number of cities is changed. The scoreboard is updated when the "new game" button is pushed after you have created a valid tour. You may undo an edge or clear your entire path without affecting your score. The radius slider can be used to find the closest city to your current location. Just crank it up until the red disk encounters its first dot, then slide it back. You may safely ignore this feature, although occasionally it can be quite useful (if you wish to pursue a "nearest neighbor" strategy, for instance). Serious gamers should hide both the distance tally and Mathematica's best tour during play.[less]
The traveling salesman problem is a famous example of an NP-complete problem. There is no known algorithm that is guaranteed to solve every -city problem in polynomial time (as a function of ). Brute force is completely impractical. The total number of possible tours when there are cities is . So, for instance, with 30 cities there are 4420880996869850977271808000000 possible tours. Suffice it to say that calculating the length of each and then identifying the shortest among them is well beyond the capacity of today's computers. It is this reality that provides the possibility of "beating" Mathematica at this game.
Mathematica uses the FindShortestTour command to find its best tour.
An excellent resource for all things TSP is William Cook's site, www.tsp.gatech.edu.