10182

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.
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.

DETAILS

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.

PERMANENT CITATION

 Share: Embed Interactive Demonstration New! Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details » Download Demonstration as CDF » Download Author Code »(preview ») Files require Wolfram CDF Player or Mathematica.

Related Topics

 RELATED RESOURCES
 The #1 tool for creating Demonstrations and anything technical. Explore anything with the first computational knowledge engine. The web's most extensive mathematics resource. An app for every course—right in the palm of your hand. Read our views on math,science, and technology. The format that makes Demonstrations (and any information) easy to share and interact with. Programs & resources for educators, schools & students. Join the initiative for modernizing math education. Walk through homework problems one step at a time, with hints to help along the way. Unlimited random practice problems and answers with built-in Step-by-step solutions. Practice online or make a printable study sheet. Knowledge-based programming for everyone.