The Traveling Salesman Problem
Image by Wystan on Flickr
Not only a funny phrase, it is a math and computer science problem that helps solve real world problems.
Computer science and mathematics have a wonderful problem called the Traveling Salesman Problem or TSP. There are variants, too, the Canadian Traveler Problem and the Chinese Postman Problem. All three problems are attempts to use math to solve ancient problems faced by people and their societies.
Imagine your name is Og and you have rocks to sell in nearby towns and villages. Your rocks are heavy and you do not want to be away from home longer than needed to sell all your rocks. Given the number of towns and villages, and the distances between each pair of villages, what would be the shortest route to visit each town or village once and return to your home?
Here is the easiest possible route if all the destinations are neatly laid out in a circle:
In this ideal world, Og can travel in a circle from A-Town to B-Town to C-Town. Or the reverse on days he (or she) gets bored.
However, this arrangement of villages is more likely:
If each dot represents a village or town, what is the shortest route Og can take to sell rocks? It’s not at all clear, is it?
Here is one way to describe the traveling salesman problem and narrow down the range of possible solutions:
In mathematical terms, the Traveling Salesman problem is a graph problem. While algorithms exist to help solve this problem, the ideal solution is difficult to find. There are so many possible alternate routes to be evaluated then compared to other routes.
Learn More
The Traveling Salesman Problem
http://mathworld.wolfram.com/TravelingSalesmanProblem.html
https://en.wikipedia.org/wiki/Travelling_salesman_problem
http://www.youtube.com/embed/BmsC6AEbkrw
Computer Scientists Find New Shortcuts for Infamous Traveling Salesman Problem
http://www.wired.com/2013/01/traveling-salesman-problem/all/
Canadian Traveler Problem
https://en.wikipedia.org/wiki/Canadian_traveller_problem
Chinese Postman Problem
https://en.wikipedia.org/wiki/Route_inspection_problem
Author
Also In The August 2014 Issue
Krissy Venosdale and Skype in the classroom
Here's an enthusiastic teacher using technology to help her students discover how the world is an awesome place to explore.
SketchUp for Beginners
It's not hard to create simple three-dimensional objects and buildings with SketchUp software. Here's a simple introduction with lots of links to learn more.
Computer Science Curriculum Resources
Resources to learn about national standards for computer science and how to implement them in the classroom.
Principle of Least Astonishment
The Principle of Least Astonishment sounds very Monty Python. But it is a key concept in software and interface design.
Music from Garbage
People do amazing things with technology, in this case, creating music from tossed out computer hard drives, circuit boards, and other electronic garbage.
Regular Expressions
All programming languages have a way to find Elvis, but it can be difficult to learn how.
3D Software Tools and Resources
3D software is a fun way to engage people interested in computing but not necessarily coding or computer science.
Programming Languages for Education
Many languages have been created for younger kids and to help teachers in a classroom setting.
If you want to build a ship, don’t drum up people together to collect wood and don’t assign them tasks and work, but rather teach them to long for the endless immensity of the sea.
August 2014 Learn More Links
Links from the bottom of all the August 2014 articles, collected in one place for you to print, share, or bookmark.
August 2014 News Wire
Interesting stories about computer science, software programming, and technology for August 2014.
LOGO
This language, developed in the 1960s, exists solely to introduce children to basic programming concepts and teach programming.
The Traveling Salesman Problem
Not only a funny phrase, it is a math and computer science problem that helps solve real world problems.
