Saturday, January 01, 2005

The traveling salesman problem as art


Here's a neat idea reported in Science News Online.

The traveling salesman problem (TSP) is to find the shortest route through a set of cities without visiting any city more than once—except that the route begins and ends at some city. For example, the image to the right shows an optimal route for 10 cities.

To use the traveling salesman problem in art, one constructs a grey-scale-like image of a figure by letting the number of cities in each small square contain a greater or lesser number of cities depending on whether the area is darker or lighter. Then a TSP solution will be darker in those parts of the image with more cities. The image to the left illustrates.

No comments: