Beam search

Beam search is a heuristic algorithm applied on a tree. It's very similar to breadth-first search, but it keeps $p$ best candidates at each $k$ level of the tree.

We can define parameters like:

• How many candidates we keep
• How deep we go below the tree's levels

Complexity

Beam search's time complexity is $O(k\times p\times n²)$