Click for more information

CMSC 451
Design and Analysis of Computer Algorithms
Dave Mount
Fall 2003



About the Image


The image shown on the class web page is a cropped image of a traveling salesman tour (TSP) of a number of sites distributed throughout Germany. The traveling salesman problem involves computing the shortest cycle that visits every one of a given set of points. (The cycle in this case is the boundary between the blue and white regions.) The TSP problem is a famous example of an NP-hard optimization problem. An image showing the entire tour is shown below.

This image was downloaded from the Princeton TSP page.

TSP Tour