User Tools

    To create and edit articles, please register and log-in

Main Menu : categories & index etc.

Main menu
Click categories to expand


A-Z listingplugin-autotooltip__plain plugin-autotooltip_bigA-Z listing

This is an alphabetical index of all content pages.


Other categories

Utilities

Contact
Register
Sandbox

Also see

Importance Ratings
News
Legal
Donate/Sponsor
Curator's rationale
AI Policy



Twitter feed 𝕏



Feeds + s.e.o. etc.
rss / xml feed
sitemap file
A-Z listing (archived)


Indexed under : Mathematics

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 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 !

Dear reader : Do you have any suggestions for the site's content?

Ideas for new topics, and suggested additions / corrections for older ones, are always welcome.

If you have skills or interests in a particular field, and have suggestions for Wikenigma, get in touch !


Or, if you'd like to become a regular contributor . . . request a login password. Registered users can edit the entire content of the site, and also create new pages.

( The 'Notes for contributors' section in the main menu has further information and guidelines etc.)

Automatic Translation

You are currently viewing an auto-translated version of Wikenigma

Please be aware that no automatic translation engines are 100% accurate, and so the auto-translated content will very probably feature errors and omissions.

Nevertheless, Wikenigma hopes that the translated content will help to attract a wider global audience.

Show another (random) article

Further resources :

DOKUWIKI IMPLEMENTATION DESIGN BY UNIV.ORG.UK DECEMBER 2023