====== 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 [[https://en.wikipedia.org/wiki/Monte_Carlo_method|'Monte Carlo']] processes) can now tackle the  [[http://en.wikipedia.org/wiki/Travelling_salesman_problem|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 '[[content:mathematics:p_vs_np|NP]]-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 [[https://en.wikipedia.org/wiki/NP-hardness#Examples|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.

~~stars>3/5~~