Traveling Salesman Problem Examples

The classic traveling salesman problem (TSP) is a good real-world application. Excessive travel expenses can be avoided when the itinerary is designed efficiently. Solutions to a TSP involve the shortest tour found among all cites without visiting the same one twice.

I suppose using a real-world map would be more interesting, but we'd be hard-pressed to prove which tours are actually the shortest. I like the idea of using a circle on a grid, with some number of marked points along it. Each mark has its own x and y coordinates. This way we can say the relation between one point and all others is the same for all points. The algorithm doesn't know that the shortest distance is actually to follow the circle (clockwise or counterclockwise), it doesn't see a circle at all. All the algorithm sees is a handful of x and y coordinates which it has to arrange in some order.

public void footer() {
About | Contact | Privacy Policy | Terms of Service | Site Map
Copyright© 2009-2012 John McCullock. All Rights Reserved.
}