Animated Examples of Heuristic Algorithms

The travelling salesman problem (TSP) probably is the most prominent problem
in combinatorial optimization. Its simple definition along with its notorious
difficulty has stimulated (and still stimulates) many efforts to find an
efficient algorithm. Due to the NP-completeness of the TSP, only
approximate solutions can be expected. This contribution presents animated,
graphical Java-Applets of some approximate algorithms for the TSP. The applets
allow to watch the algorithms in action and to play around with them.

- 1. Introduction
- 2. Construction Heuristics
- 3. Improving Solutions
- 4. Lower Bounds
- Bibliography
- About this document ...