Beam search
| Beam search | |
|---|---|
Beam search with width 3 (animation) | |
| Class | Search algorithm |
| Data structure | Graph |
| Worst-case performance | O(depth * beamWidth * maxFanout * Log(beamWidth * maxFanout)) |
| Worst-case space complexity | O(beamWidth * maxFanout) |
| Optimal | No |
| Complete | No |
In computer science, beam search is a heuristic search algorithm that explores a graph by expanding the most promising node in a limited set. Beam search is a modification of best-first search that reduces its memory requirements. Best-first search is a graph search which orders all partial solutions (states) according to some heuristic. But in beam search, only a predetermined number of best partial solutions are kept as candidates. It is thus a greedy algorithm.