Bill Cook sent me a file yesterday that renders the Endeavour photo on my blog as the solution to a 66,290-city Traveling Salesman problem. His iPhone app Concord TSP chose 66,290 points and then solved for the shortest path connecting these points, a feat that would have strained a supercomputer a few years ago. (Bill Cook and I are not related as far as I know.)
Here is a thumbnail image of the full TSP tour:
You can find the full PDF here (1.24 MB). To show some of the detail, here is a close-up from near the top-left corner of the image:
I asked how the tour was constructed:
How do you construct a set of points whose TSP solution resembles a photograph? Is it sufficient to add more “cities” in regions where you want darker shading? And are the cities added at random with a density specified by color depth?
Bill Cook replied:
By default, the app will select the points along the line you describe: it splits the image into a grid, computes the average gray scale in each grid region, and drops a number of random cities into each grid region in proportion to the square of the average gray scale. This technique was first proposed by Bob Bosch and Adrianne Herman at Oberlin College. It is the default since it takes almost no time to compute, but I include two other options, that each take about a minute to render a large image on an iPhone 4.
The image of The Endeavour was created with a method Jim Bumgarnder proposed in his Stipple Cam project.
Related post: Moore’s law squared
This is fascinating. Is this the precise solution to this 66,290-city Traveling Salesman problem, or merely a good solution? I had no idea such large Traveling Salesman problems were computer solvable in such a short time. What has changed in recent years that a problem that would strain supercomputers a few years ago can now be whipped out by an iPhone app?
Presumably, this is *not* a provably optimal TSP solution.
The tour was found with 500 iterations of the Chained-Lin-Kernighan heuristic. It typically gives a very good solution, but not optimal for such a large instance.
I can think of a use for this algorithm: sending raster images to vector printers! Both laser printers and pen plotters use line paths to turn greyscale raster images into two-tone plots which they can scan with their pen/laser.
Why travelling salesman? Well, a shorter path should be quicker to print, and it doesn’t need to be optimal, just reasonable.
Who’s got a plotter?
Very cool. ;-)
If you poke two holes in the edges of the TSP solution you wind up with a maze, since an optimal or near-optimal planar TSP solution can be continuously deformed without crossing into a circle. (Otherwise you can hill climb by swapping some edges to make a better solution and concorde is smart enough to have already done so)
I used this approach (and concorde for what its worth) several years back to make mazes for a linguist list fund drive out of images and there has been at least one paper written on the topic.
The nice thing is you get to know that a solution exists, but you don’t get direct knowledge of what the solution is — not that it is that hard to find with a pathfinding algorithm after the fact.
There is, sadly, some bias in this approach though, since the number of points in a given unit area is only fairly loosely correlated to the amount of ink spent on paths moving through that area.
You may also be interested in the first paper I saw on the topic:
http://www.cgl.uwaterloo.ca/~csk/papers/kaplan_bridges2005b.pdf
This method of generating greyscale »images« was recently also mentioned over at Evil Mad Scientist Labs. There the problem was essentially how to draw an image efficiently on an egg, where TSP paths provide a nice solution that does not need any pen lifting while still providing lighter and darker areas in the image.