No description or website provided.
Switch branches/tags
Nothing to show
Clone or download
Latest commit 1f5321e Oct 17, 2018
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
48 cities demo 15000 miles Update README.dm Oct 16, 2018
Nearestneighbor.gif Add files via upload Oct 13, 2018
README.md Update README.md Oct 17, 2018
TSP_ATT48_SA.epl Create TSP_ATT48_SA.epl Oct 16, 2018
waitingcat.gif Add files via upload Oct 13, 2018
world.anim1a.gif Add files via upload Oct 13, 2018

README.md

Claim your 3000 XEL

Traveling Salesman Problem

ATT48 is a set of 48 cities (US state capitals) from TSPLIB. The minimal tour has length 10628 .

The travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?" It is an NP-hard problem in combinatorial optimization, important in operations research and theoretical computer science.

The travelling purchaser problem and the vehicle routing problem are both generalizations of TSP.

In the theory of computational complexity, the decision version of the TSP (where, given a length L, the task is to decide whether the graph has any tour shorter than L) belongs to the class of NP-complete problems. Thus, it is possible that the worst-case running time for any algorithm for the TSP increases superpolynomially (but no more than exponentially) with the number of cities.