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

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.

Tags:

* entertainment * pop culture * Computer Science * Mathematics * Engineering * network theory

* research and design * traveling salesman * TSP * microprocessor * NP complete * algorithms

* approximations * technology

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.

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.

Tags:

* entertainment * pop culture * Computer Science * Mathematics * Engineering * network theory

* research and design * traveling salesman * TSP * microprocessor * NP complete * algorithms

* approximations * technology

## 4 Comments:

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

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.

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

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

Post a Comment

## Links to this post:

Create a Link

<< Main