> My solution's similar in style [breadth first, don't duplicate search],
> though I've also roof-limited it so it can't explore the search space
> above 2*[max(target,start)] + 4 which provides a fair speed up for e.g.
> 222, 9999.  I'm not sure if that loses the optimality property though.

I use
  @@max = [(source + 2) * 2, target * 2].max
which matches your roof almost exactly (The small assymetry is due to the
missing sub2 operator, naturally.). The speedup is huge, as you can see
in some other posting of mine. I'm not entirely certain about the optimality
property, but look at the following example:

13, 15, 30, 32, 16, 8  # what I thought of myself, pushing through the roof
13, 26, 28, 14, 16, 8  # what the program found, not going through the roof

Where the point is that an odd number either +1 or +3 can always be halved
twice, and there is no point in adding two first (though maybe in between).

I'm even thinking
  [source*2+2, target*2].max 
could be the roof, but hey, what's 2 more or less.

Ah well, this is not my field of expertise. Somebody can shed more light on
this?

Bye,
Kero.