# The Traveling Salesman Problem

The traveling salesman problem is a traditional computer science challenge.
Its goal is to find the shortest circuit through a set of points.
A common approach is to construct an initial path and then improve it
incrementally through local optimizations.

The `travels.icn`

program
illustrates several construction algorithms
followed by application of the "2-opt" improvement algorithm;
that algorithm deletes two segments at a time and reconnects their endpoints.
If you look closely you may spot sections of a path that could be further
improved by the "3-opt" algorithm which is not implemented here.

## Further Reading

David S. Johnson.
Local Optimization and the Traveling Salesman Problem.
Proc. 17th Colloquium on Automata, Languages, & Programming,
Springer-Verlag (1990), pp. 446-461.

Icon home page