Beam Search Visualization & Simulator

Q: What is the complexity of beam search?

Time O(k·b·m) and space O(k·b), where b is the branching factor and m the depth reached.

About this visualization

Beam search is breadth-first search that keeps only the k most promising nodes (lowest heuristic value) at each level. It saves memory and time but is neither complete nor optimal: if the only route to the goal runs through a discarded node, the search fails.

How it works

Start with the beam containing only the start node.
Generate all successors of the beam, sort them by h and keep only the best k.
Repeat until the goal is in the beam, or no successors remain.

Formulas used

Time: $O(k\cdot b\cdot m)$ Space: $O(k\cdot b)$

Worked example

On the Romania map with k = 2 the beam goes {Arad} → {Sibiu, Timisoara} → {Fagaras, Rimnicu} → {Bucharest, Pitesti}, so the goal is in the beam at level 3, with path cost 450. On the local-minimum trap graph k = 1 fails (it behaves like hill climbing) but k = 2 succeeds.

Enter these numbers in the simulator above to see every step.

Complexity and properties

Worst case	$O(k\cdot b\cdot m)$
Space	$O(k\cdot b)$

Neither complete nor optimal. k = 1 is hill climbing; k = ∞ is breadth-first search.

When to use it

Sequence generation in machine translation and speech recognition.
Memory-bounded search in AI.
Understanding the trade-off between width and completeness.

Frequently asked questions

What is beam width?

The number of nodes kept at each level of the search. k = 1 is hill climbing; k = ∞ is breadth-first search.

Is beam search complete?

No. A node on the only path to the goal can be pruned.

What is the complexity of beam search?

Time $O(k\cdot b\cdot m)$ and space $O(k\cdot b)$ , where b is the branching factor and m the depth reached.