The Traveling Astronomer Problem

Apropos of something I'm not quite ready to talk about, here is an interesting challenge:

How do you optimize your time at the telescope if you have a set of objects that you'd like to observe?

For instance, if you want to see as many Messier objects as you can in a single night, a portion of your night might use this sequence, suggested in the book "Messier Marathon Observer's Guide"

screen-shot-2010-09-16-at-104738-am

On the other hand, it looks like there's a wasteful jog near Serpens Cauda -- near the label "18h30m" in the image. That jog is the recommended sequence "M24-M25-M23" but if minimizing the path were the only criterion, it looks like it would be quicker to visit M25 "on the way" between M7 in Scorpius and M11 in Scutum.

Now, by no means do I want to be so presumptuous to suggest that Machholz "made a mistake" in his recommended order. Minimizing the path is not the only or even overwhelmingly-dominant criterion -- if you're really doing the Messier marathon, it's customary to do it without the help of a computerized "goto" system and using easy-to-find objects and straight line "star hops" is a big deal.

Similarly, in the real world you're going to be battling light pollution, clouds, and terrestrial obstructions.

But this visualization that I made using Google Earth and some Ruby code does suggest that it might be worth using the power of a computer to help you plan your evening's viewing.

The bad news is that there are lots of possible paths one can take between all 110 Messier objects -- 1588245541522742940425370312709077287172441023447356320758174831844456\
7162948183030959960131517678520479243672638179990208521148623422266876\
757623911219200000000000000000000000000 paths. Most of those paths are impossible for an Earth-based scope (as a matter of fact, there are only brief windows during the year when all the Messier objects are visible at night from a given location). And most paths could be rejected very quickly. But still, no matter how quickly you evaluate a path, there's no way to use a computer to find the absolute shortest path between this many cities... er ... graph nodes ... er ... sky targets.

The good news is that there are all sorts of wicked cool ways to find "pretty good" paths.