How Beam Search Works
Beam search explores level by level like breadth-first search, but keeps only the few most promising candidates at each level and forgets the rest. Memory stays fixed; the shortest route is no longer guaranteed, and sometimes no route is found at all.
Complexity
| Best | Average | Worst | Extra memory |
|---|---|---|---|
| O(B · d) | O(B · d · log B) | O(B · d · log B) | O(B) |
B is the beam width and d the number of levels. The frontier never holds more than B entries, which is the whole point; the visited set used here to stop cycles is extra.
How beam search works
Beam search expands every intersection in the current level, gathers all their unseen neighbours, scores them by distance travelled plus straight-line distance left, and keeps only the best B for the next level. Everything else is dropped for good. A wide beam behaves like breadth-first search guided by a heuristic; a beam of width one is a greedy walk. In between, it trades completeness and optimality for a bound on memory that does not depend on the size of the graph.
- The first level is just the start.
- Expand every intersection in the level. If one of them is the goal, walk the parents back.
- Collect the unseen neighbours of the whole level and score each by g + h.
- Keep the best B of them as the next level and discard the rest permanently.
When to use it
- Use it when the search space is too large to hold, and a good answer beats no answer: machine translation and speech decoding are the classic cases.
- Avoid it when the route has to be the shortest or has to exist. A narrow beam can prune the only way around a lake.
Check yourself
Why can beam search fail to find a route even though one exists?
Because pruned candidates are gone for good. If every way through a bottleneck falls outside the best B at some level, nothing left in the beam can reach the goal.