Beam search

But in beam search, only a predetermined number of best partial solutions are kept as candidates.

The greater the beam width, the fewer states are pruned.

[3] Conversely, a beam width of 1 corresponds to a hill-climbing algorithm.

[3] The beam width bounds the memory required to perform the search.

Since a goal state could potentially be pruned, beam search sacrifices completeness (the guarantee that an algorithm will terminate with a solution, if one exists).

Beam search is not optimal (that is, there is no guarantee that it will find the best solution).

The Harpy Speech Recognition System (introduced in a 1976 dissertation[6]) was the first use of what would become known as beam search.

randomly generated states and then, for each level of the search tree, it always considers