Difference between revisions of "Travelling salesman problem"
Jump to navigation
Jump to search
(Created page with "The '''Traveling Salesman Problem''' is a classical NP-hard problem in computational mathematics. Its goal is to find the cheapest path between an arbitrarily large number of cit...") |
|||
| Line 7: | Line 7: | ||
==External Links== | ==External Links== | ||
| − | [http://www.tsp.gatech.edu/index.html The Traveling Salesman Problem at Georgia Tech] | + | *[http://www.tsp.gatech.edu/index.html The Traveling Salesman Problem at Georgia Tech] |
| − | + | *[http://xlinux.nist.gov/dads/HTML/travelingSalesman.html Information on TSP from NIST] | |
[[category:Computer Science]] | [[category:Computer Science]] | ||
Revision as of 01:43, October 6, 2011
The Traveling Salesman Problem is a classical NP-hard problem in computational mathematics. Its goal is to find the cheapest path between an arbitrarily large number of cities.
In the simplest implementation, the cost of travel is defined as the distance between the cities. While the problem seems simple, it has no general solution; indeed, solving it would resolve the P vs. NP issue in general computer science. As is the case with many classical 'toy' problems in computer science, studying the TSP has lead to improved solutions in many other areas.[1]