3
edits
Changes
Jump to navigation
Jump to search
Travelling salesman problem (view source)
Revision as of 01:34, October 6, 2011
, 01:34, October 6, 2011Created 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..."
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.<ref>http://www.tsp.gatech.edu/problem/index.html</ref>
==References==
<references />
==External Links==
[http://www.tsp.gatech.edu/index.html The Traveling Salesman Problem at Georgia Tech]
[[category:Computer Science]]
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.<ref>http://www.tsp.gatech.edu/problem/index.html</ref>
==References==
<references />
==External Links==
[http://www.tsp.gatech.edu/index.html The Traveling Salesman Problem at Georgia Tech]
[[category:Computer Science]]