Beam search

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


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Beam Search —    Main branches of antlers from which the forks grow …   Hunting glossary

  • Beam stack search — is a search algorithm which integrates backtracking with beam search.It was recently proposed by Rong Zhou and Eric A. Hansen, Department of Computer Science and Engineering, Mississippi State University during the 15th International Conference… …   Wikipedia

  • search|light — «SURCH LYT», noun. 1. a powerful light that can throw a very bright beam of light in any direction. 2. the beam of light so thrown: »The searchlights had begun their nightly wanderings (John Galsworthy) …   Useful english dictionary

  • Search for extraterrestrial intelligence — The search for extraterrestrial intelligence is sometimes abbreviated as SETI. For other uses, see SETI (disambiguation). Screen shot of the screensaver for SETI@home, a distributed computing project in which volunteers donate idle computer power …   Wikipedia

  • Search and Rescue (Stargate Atlantis) — Infobox Television episode Title = Search and Rescue Series = Stargate Atlantis Caption = Sheppard, Dex and McKay prepare to infiltrate Michael s cruiser. Season = 5 Episode = 1 Writer = Martin Gero Director = Andy Mikita Guests = Rainbow Sun… …   Wikipedia

  • Best-first search — is a search algorithm which explores a graph by expanding the most promising node chosen according to some rule.Judea Pearl described best first search as estimating the promise of node n by a heuristic evaluation function f(n) which, in general …   Wikipedia

  • Stack search — (also known as Stack decoding algorithm) is a search algorithm similar to beam search. It can be used to explore tree structured search spaces and is often employed in Natural language processing applications, such as parsing of natural languages …   Wikipedia

  • Lazer Beam — Infobox Single Name = Lazer Beam Artist = Super Furry Animals from Album = Love Kraft Released = 15 August 2005 Format = Digipack CD, 7 Recorded = Genre = Alternative rock Length =4:55 (Album version) 3:36 (Radio edit) Label = Epic Records Writer …   Wikipedia

  • Cuckoo search — (CS) is an optimization algorithm developed by Xin she Yang and Suash Deb in 2009.[1][2] It was inspired by the obligate brood parasitism of some cuckoo species by laying their eggs in the nests of other host birds (of other species). Some host… …   Wikipedia

  • Depth-first search — Order in which the nodes are visited Class Search algorithm Data structure Graph Worst case performance …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”