Beam search is an informed, memory-bounded variant of BFS. It reduces the memory cost of BFS, using heuristic information to guide expansion, trading away guarantees for scalability.
Essentially, at each depth we only expand the top nodes. is called the beam width and is the maximum number of nodes retained per level. Nodes are ranked using an evaluation function; all other nodes are discarded permanently.
Properties
- Complete: No (may discard the only solution path)
- Optimal: No (even with admissible heuristics)
- Time complexity:
- Space complexity:
Example
