TSP Algorithms in Action
Animated Examples of Heuristic Algorithms

Stephan Mertens

Abstract:

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.