Travelling Salesman Problem
This is an old revision of this page, as edited by JOwen (talk | contribs) at 20:35, December 28, 2007. It may differ significantly from current revision.
The Travelling Salesman Problem is a problem that seeks to find the shortest way of getting through a network, starting from any point, visiting every other point, in the shortest time. It is commonly modelled as a network of arcs and nodes.
It is a common example of an algorithm that has to be solved heuristically; while it is possible to solve it with brute force, by trying every single route and finding the shortest, this is impractical, since the number of routes increases factorially; while a 3-node network has only 6 routes, a 10-node one has 3,628,800.