Beam search nearest neighbors

A common problem is finding the nearest neighbors of a given object in some search space. Beam search is an “anytime” heuristic search algorithm which very efficiently accomplishes this.

Imagine we have a set of N nodes, each randomly “closest” (connected by an edge) to n other nodes. The algorithm works as follows:

1. Pick a node; paint it red.
2. Paint its neighbors grey. Also paint the neighbors for each of those neighbors.
3. “Fix” the edges of the red node by connecting it to the closest of these grey nodes.
4. Repeat for each node.