In 1977, Turing Award Winner Dr Raj Reddy of Carnegie Mellon University came up with the term "beam search." Beam search is a best-first search optimization that reduces memory requirements. Best-first search is a graph search that ranks all partial solutions (states) based on a heuristic. However, only a predetermined number of the best partial solutions are retained as candidates in beam search. As a result, it is a greedy algorithm.

Structure

Beam search constructs its search tree using breadth-first search. It generates all successors of the states at the current level at each level of the tree, sorting them in increasing order of heuristic cost. However, it only saves a limited number of the best states at each level (called the beam width). Following that, It will expand only to those states. The more states that are pruned, the wider the beam. No states are pruned when the beam width is infinite, and beam search is identical to breadth-first search. 

Furthermore, the beam width limits the amount of memory required to perform the search. Finally, because it may prune a goal state, beam search sacrifices completeness (the guarantee that an algorithm will terminate with a solution if one exists). As a result, beam search is inefficient (that is, there is no guarantee that it will find the best solution).

Beam Search has different parts:

• A problem to figure out,
• A set of rules to follow when pruning,
• And a memory that can only hold so much.

The problem is the problem that needs to be solved. It is usually shown as a graph and has a set of nodes, each of which is a goal. The heuristic rules are made up of rules specific to the problem domain and eliminate unhelpful nodes in memory.

The "beam" is stored in the memory. If the memory is complete and a node needs to be added to the beam, the most expensive node will be removed so that the memory limit isn't reached.

Uses

A beam search is commonly used to maintain tractability in large systems where memory is insufficient to store the entire search tree. 

• It is used in many machine translation systems, for example. (The current state of the art primarily employs neural machine translation-based methods.) 
• Each part is processed to find the best translation, and many different ways of translating the words appear. 

Moreover, the best translations are kept based on their sentence structures, while the rest are discarded. The translator then evaluates the translations using a predefined criterion, selecting the translation that best achieves the goals. The Harpy Speech Recognition System, CMU 1976, was the first to use a beam search.

Conclusion

Combining beam search with depth-first search led to beam stack search and depth-first beam search. Combining beam search with limited discrepancy search led to beam search using limited discrepancy backtracking (BULB). The resulting search algorithms are like beam search, which finds reasonable but likely sub-optimal solutions, then goes back and keeps looking for better solutions until they find the best one.

Furthermore, Local beam search often ends up on local maxima, so one standard solution is to pick the following states randomly, with the probability depending on how it evaluated them heuristically. The name for this type of search is "stochastic beam search." Moreover, the flexible beam search and the recovery beam search are two other kinds.