!<blog/meet-in-the-middle?12fig26.gif 60%! The usual approach is to use a bread first search algorithm. If the distance between two nodes is $k$ and the average degree in the network is $p$ then we explore $O(p^k^)$ nodes.

One neat idea is instead of starting the search from one node, start from both and see when the two search spaces meet.  This way we only go through $O(p^k/2^)$ nodes.

A better solution starts from both nodes and sees when the two search spaces meet.  The improvement is that you only explore $O(p^k/2^)$ nodes.

This approach works well on both path finding problems on explicit graphs and on implicit state graphs like ones in games.

The approach works well with both path finding problems on explicit graphs and with implicit state graphs like the ones you find in games.

h2. Caveats