beanz Magazine

The Traveling Salesman Problem

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:

Example of traveling salesman path
The Perfect Route for Og, Traveling Salesman

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:

More realistic traveling salesman path
A More Likely Map of Towns and Villages

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

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.