A traveling salesman must visit customers in a given number of cities scattered across the country. The problem is to find the shortest route that takes the traveler just once to each city before returning home.
Listing all possible routes, calculating the length of each one, and picking the shortest is one possible strategy for solving the problem. For a large number of cities, however, such a brute-force approach requires a huge amount of computation.
For example, to find the shortest possible route to visit 10 cities, a computer would have to evaluate 362,880 (9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1) possibilities. As the number of cities increases, the number of possible routes skyrockets.
Nonetheless, researchers have found ways to compute optimal tours for a remarkably large number of cities. The current record-holder, computed in May, 2004, is a tour that visits all 24,978 cities, towns, and villages in Sweden (see http://www.tsp.gatech.edu/sweden/index.html). The route is about 72,500 kilometers long. No shorter route is possible.
This record tour was found by David Applegate of AT&T Labs–Research, Robert Bixby of Rice University, Vaek Chvátal of Rutgers University, William Cook of Georgia Tech, and Keld Helsgaun of Roskilde University.
Mathematician Robert Bosch and student Adrianne Herman of Oberlin College in Ohio have now developed a computer program that brings the traveling salesman problem into the world of art. They use the routes that result from solving the problem to create continuous-line drawings.
Art teachers are fond of asking beginning students to make such drawings. The idea is to look at an object, place the tip of your pencil on a sheet of paper, then make a drawing of the object without letting the pencil’s tip leave the paper until the picture is finished. That’s a lot like finding an optimal route that links a large number of cities.
Bosch and Herman start with a black-and-white digital image. Each pixel of the image has a grayscale value between 0 (completely black) and 255 (completely white). The picture is then divided into squares, each one consisting of a block of pixels. Next, the average darkness of each square is computed.
A blank digital “canvas” is then divided into squares to match those of the original image. The computer randomly places points (representing cities) within each square in such a way that the points are uniformly distributed within the square. The number of points placed in each square is related to the square’s darkness. Distances between the points are then computed.
To find an approximate solution to the corresponding traveling salesman problem, Bosch and Herman use a method developed by the same group that recently found the record tour. The resulting tour is a continuous-line drawing of the target image.
Bosch has used the technique to create a number of continuous-line portraits, including ones of Marilyn Monroe and other people. His artful routes sometimes involve more than 100,000 cities.
So, the same sorts of techniques used for solving optimization problems—which range from routing telephone calls and constructing schedules to allocating resources and designing networks—can also play a role in creating ingenious artworks.
