bq. Find the shortest path between two nodes nodes in a large graph which you can’t keep in memory, for example the Facebook friendship graph.

!<blog/meet-in-the-middle?12fig26.gif 80%! 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.

!<blog/meet-in-the-middle?12fig26.gif 80%! The breadth first search algorithm is a standard approach for this problem. If the distance between two nodes is $k$ and the average degree in the network is $p$ BFS explores $O(p^k^)$ 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.

A better solution starts from both nodes and sees when the two search spaces meet.  This reduces the number of states explored to $O(p^k/2^)$.

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

Unlike divide and conquer the trick in meet in the middle can't be applied recursively because the sub problems don't have the same structure as the original problem.

Unlike divide and conquer meet in the middle can't be applied recursively because the sub problems don't have the same structure as the original problem.

Bidirectional search can be often replaced by some search algorithm that uses some heuristics like A*.
h2. Additional problems