Travelling Salesman Problem

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]

References[edit]

1. ↑ http://www.tsp.gatech.edu/problem/index.html

External links[edit]

• The Traveling Salesman Problem at Georgia Tech
• Information on TSP from NIST