ABSTRACT
The Traveling Salesman Problem (TSP) involves constructing a minimum distance tour that visits each city exactly once and returns to the starting point. As well as its applications to puzzles, the TSP underlies a variety of problems in which we need to determine an optimal ordering: for example, manufacturing a circuit board or determining a likely chronology for archaeological finds. Unlike the previously encountered shortest path problem and the Eulerian circuit problem, there are no known solution techniques that can solve every TSP efficiently. As a result, a number of heuristic (approximate) techniques have been developed to find good, though not necessarily optimal, solutions.
