Random article ( of 1064 ) Latest updates

User Tools

Site Tools


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

The 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 just once and returns to the origin city?

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

The problem has been examined since the 1930s. but a formal mathematical 'proof' - which could enable a quick and exact computation, has not yet been found.

From a computational standpoint the problem is known to be 'NPplugin-autotooltip__plain plugin-autotooltip_bigThe 'P versus NP' problem

The 'P versus NP' problem is a major unsolved enigma in mathematical computer science,

It was first described in 1971 by mathematician Stephen Cook in his paper entitled 'The complexity of theorem-proving procedures' Proceedings of the Third Annual ACM Symposium on Theory of Computing
-hard ' - that's to say that there is a way to find a solution to the problem. But on a large scale it can be computationally impractical for a computer program to iterate though the every possible combination and check if it's the best possible route (see Wikipedia for more NP-hard info.).

Aside from its mathematical interest, a non-iterative formula for solving the problem would have many real-world applications - not just for transport logistics, but also for electronic chip layout design, DNA sequencing and etc..

Note: As mentioned above, small-scale versions of the problem, where there is a reasonable computing time to check every possible route, it will, of course be possible to reveal the most efficient route.

Importance Rating

Show another (random) article

Suggestions for corrections and ideas for articles are welcomed : Get in touch!

Further resources :

Do NOT follow this link or you will be banned from the site!