Better distance estimates and better graphs can push A* to work on larger problems. ALT gives better distance estimates: http://research.microsoft.com/pubs/6451

Better distance estimates and better graphs can push A* to work on larger problems. ALT gives better distance estimates: http://research.microsoft.com/pubs/64511/tr-2004-24.pdf http://research.microsoft.com/pubs/64511/tr-2004-24.pdf (PDF link) (or these slides http://www.cs.princeton.edu/courses/archive/spr09/cos423/Lectures/reach-mit.pdf http://www.cs.princeton.edu/courses/archive/spr09/cos423/Lec... ). Transit nodes do too, I think. Contraction hierarchies and arc flags let you preprocess the graph to give better information to A*. (I've not implemented any of these myself)