Beam search

Beam search is a heuristic search algorithm that is an optimization of best-first search that reduces its memory requirement. Best-first search is a graph search which orders all partial solutions (states) according to some heuristic which attempts to predict how close a partial solution is to a complete solution (goal state). [Xu, Yuehua. Fern, Alan. "On Learning Linear Ranking Functions for Beam Search". http://www.machinelearning.org/proceedings/icml2007/papers/168.pdf] In beam search, only a predetermined number of best partial solutions are kept as candidates. [ [http://foldoc.org/index.cgi?query=beam+search&action=Search beam search from FOLDOC ] ]

Beam search uses breadth-first search to build its search tree. At each level of the tree, it generates all successors of the states at the current level, sorts them in order of increasing heuristic values. [ [http://bradley.bradley.edu/~chris/searches.html British Museum Search ] ] However, it only stores a predetermined number of states at each level (called the beam width). The smaller the beam width, the more states are pruned. Therefore, with an infinite beam width, no states are pruned and beam search is identical to breadth-first search. The beam width bounds the memory required to perform the search, at the expense of risking completeness (possibility that it will not terminate) and optimality (possibility that it will not find the best solution). The reason for this risk is that the goal state could potentially be pruned.

Uses

A beam search is most often used to maintain tractability in large systems with insufficient amount of memory to store the entire search tree. [Furcy, David. Koenig, Sven. "Limited Discrepancy Beam Search". http://www.ijcai.org/papers/0596.pdf] For example, it is used in many machine translation systems. [Tillmann, Christoph. Ney, Hermann. "Word Reordering and a Dynamic Programming Beam Search Algorithm for Statistical Machine Translation". http://acl.ldc.upenn.edu/J/J03/J03-1005.pdf] To select the best translation, each part is processed, and many different ways of translating the words appear. The top best translations according to their sentence structures are kept and the rest are discarded. The translator then evaluates the translations according to a given criteria, choosing the translation which best keeps the goals.

It has also been used in an implementation of the game five in a row. A list of possible successors to win the game is built and categorized threats are evaluated. A criterion of this game is whether or not the computer needs to adjust its strategies depending on how many possibilities the person playing the computer has to win. [Chen, Jiun-Hung. Wang, Adrienne X. "Five-In-Row with Local Evaluation and Beam Search"]

References

See also

*Beam stack search