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' 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…-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 to iterate though the every possible combination and checking if it's the best 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, and DNA sequencing etc. etc..

Note: As noted 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

---

Please share this page to help promote Wikenigma !