Tuesday, February 13, 2007

Traveling Salesman Problem

I've always been somewhat fascinated by the Traveling Salesman problem, which is an example of a hard to solve Computer Science/Mathematical problem. Essentially the problem boils down to this:

Given a number of cities and the costs of traveling from any city to any other city, what is the cheapest round-trip route that visits each city exactly once and then returns to the starting city?

The problem can be illustrated as a graph where each city is a point in the graph and the cities are all connected by lines (edges). The edges are weighted by costs to travel from one city to the other city.
Example of an "Easy" Traveling Salesman Graph

The greater the number of cities (points), the more challenging it is to come up with the best solution. Further constraints can be added, which can make the problem even more difficult to solve.

Solution to the Traveling Salesman problem in respects to major USA cities.

Over the years, there has been many different algorithms developed to solve this problem quickly. Although these algorithms provide a solution, they do not yield the best solution. In order to get the best solution, every combination must be explored. Nevertheless, innovative approximations can be very useful in the engineering world especially in respect to network theory and microprocessor design.

* * * * * *
* * * * * *
* *


Blogger Tom G said...

You are such a dork!!! I mean that in the most praiseworthy tone possible.

2/14/2007 11:29:00 AM  
Blogger Mike K said...

Heh. Yeah. I am. The complexity of finding the best solution is 0(n!) where n is the number of cities. That is madness! Using some tricks, the time can be cut down to O(2^n).

Try finding the solution if it is only 100 cities. There are only 1,267,650,600,228,229,401,496,703,205,376 combinations. Even ten cities is 1,024 combinations.

2/14/2007 04:12:00 PM  
Anonymous Anonymous said...

I second that. I played around with a simulation (win32 executable freeware, no installation). There you can watch routes optimizing...

2/21/2007 08:41:00 AM  
Blogger Mike K said...

That is pretty cool. I'm going to have to check that out.

2/27/2007 11:05:00 AM  

Post a Comment

Links to this post:

Create a Link

<< Main

Life is Crap: A blog covering: humor, news, politics, music, movies, tv, sports, and other things.
Questions? Comments? Death Threats? Suggestions? Contact us: thecrapspot@yahoo.com
(Home) (Archives) (Next page) (Subscribe to Life is Crap)