Difference between revisions of "Travelling salesman problem"
Jump to navigation
Jump to search
DavidB4-bot (talk | contribs) m (→External links: clean up) |
|||
| Line 6: | Line 6: | ||
<references /> | <references /> | ||
| − | ==External | + | ==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] | *[http://xlinux.nist.gov/dads/HTML/travelingSalesman.html Information on TSP from NIST] | ||
| − | [[ | + | [[Category:Computer Science]] |
Latest revision as of 15:04, June 23, 2016
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]