Beam search

From Wikipedia, the free encyclopedia

Beam search is a heuristic search algorithm that is an optimization of best-first search. It was conceived as an optimization of best first search, a graph search which clusters all current paths according to some heuristic which attempts to predict how close the end of a path is to a solution. However, the problem of memory consumption arises [1]. In this type of search, only a predetermined number of paths are kept as candidates[2].

It uses a breadth-first to build its trees but keeps a certain number of trees with the smallest heuristic number between a goal node and the originating node. Unlike breadth-first search, it only moves downward from the best nodes at each level[3]. The smaller the beam width, the more steps are pruned. However, the danger of this is that excessive pruning can prevent any steps from being formed. When it does this, it risks completeness and optimality. When beam search expands a level, it generates all successors of the states at the current level, sorts them in order of increasing heuristic values.

[edit] Uses

A beam search is most frequently used to maintain tractability in large systems [4]. For example, many word translators use this [5]. To select the best translation, each part is processed, and many different ways of translating the words appear. The translations which according to sentence structure appear to be the best are kept and the rest are disposed of. The translator then figures out, according to the given criteria which is the best translation. The best one is the one which best keeps the goals.

Another implementation is the game five in a row. They build a list of possible successors to win the game, evaluating threats which are categorized. A criterion of this game is whether or not the computer needs to adjust depending on how many possibilities the person playing the computer has to win[6].

[edit] References

  1. ^ Xu, Yuehua. Fern, Alan. "On Learning Linear Ranking Functions for Beam Search". http://www.machinelearning.org/proceedings/icml2007/papers/168.pdf
  2. ^ beam search from FOLDOC
  3. ^ British Museum Search
  4. ^ Furcy, David. Koenig, Sven. "Limited Discrepancy Beam Search". http://www.ijcai.org/papers/0596.pdf
  5. ^ 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
  6. ^ Chen, Jiun-Hung. Wang, Adrienne X. "Five-In-Row with Local Evaluation and Beam Search"

[edit] See also