User Tools

Site Tools

Please register and/or login to edit and create pages


Click here to display navigation menu

start:mathematics:travelling_salesman

Wikenigma - an Encyclopedia of Unknowns Wikenigma - an Encyclopedia of the Unknown Wikenigma - an Encyclopaedia of Unknowns Wikenigma - an Encyclopaedia of the Unknown

Travelling salesman problem

Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?

Computing algorithms (using so-called 'Monte Carlo''Monte Carlo' processes) can now tackle the Travelling Salesman Problem with thousands of destinations and give an almost exact answer.

But a formal mathematical 'proof' - which could enable an exact computation, has not yet been found.

Note: Small-scale versions of the problem, where there is enough time to check every possible route, will, of course reveal the most efficient route.


DOKUWIKI IMPLEMENTATION DESIGN BY UNIV.ORG.UK