Content deleted Content added
Undid revision 1188649871 by DMH223344 (talk) - please cite sources and be more specific - "backtracking algorithm" in what sense? Also note that this case is already discussed below ("With an infinite beam width ...") |
+illustration / citation formatting / directly link source instead of a search page / such a primary source is not a suitable reference for this kind of primacy claim |
||
Line 1:
{{short description|Heuristic search algorithm}}
[[File:Beam search.gif|thumb|Beam search with width 3 (animation)]]
In [[computer science]], '''beam search''' is a [[heuristic (computer science)|heuristic]] [[search algorithm]] that explores a graph by expanding the most promising node in a limited set. Beam search is an optimization of [[best-first search]] that reduces its memory requirements. Best-first search is a graph search which orders all partial solutions (states) according to some heuristic. But in beam search, only a predetermined number of best partial solutions are kept as candidates.<ref>{{Cite web |title=beam search |url=
The term "beam search" was coined by [[Raj Reddy]] of [[Carnegie Mellon University]] in 1977.<ref>{{Cite book |last=Defense Technical Information Center |url=http://archive.org/details/DTIC_ADA049288 |title=DTIC ADA049288: Speech Understanding Systems. Summary of Results of the Five-Year Research Effort at Carnegie-Mellon University |date=1977-08-01 |language=english}}</ref>
== Details ==
Beam search uses [[breadth-first search]] to build its [[Tree traversal|search tree]]. At each level of the tree, it generates all successors of the states at the current level, sorting them in increasing order of heuristic cost.<ref>{{Cite web|url=http://bradley.bradley.edu/~chris/searches.html|title=BRITISH MUSEUM SEARCH|website=bradley.bradley.edu|access-date=2016-04-11}}</ref> However, it only stores a predetermined number, <math>\beta</math>, of best states at each level (called the beam width). Only those states are expanded next. The greater the beam width, the fewer states are pruned. 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. 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).<ref>{{Cite book|url=https://books.google.com/books?id=X4mhySvjqUAC|title=Paradigms of Artificial Intelligence Programming: Case Studies in Common LISP|last=Norvig|first=Peter|date=1992 |publisher=Morgan Kaufmann|isbn=9781558601918 }}</ref>
== 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.<ref name="furcy"/> For example, it has been used in many [[machine translation]] systems.<ref>{{cite journal |last1=Tillmann |first1=C. |last2=Ney |first2=H. |title=Word reordering and a dynamic programming beam search algorithm for statistical machine translation |journal=Computational Linguistics |volume=29 |issue=1 |pages=97–133 |date=2003 |doi= 10.1162/089120103321337458|s2cid=7829066 |url=https://direct.mit.edu/coli/article-abstract/29/1/97/1794|doi-access=free }}</ref> (The state of the art now primarily uses [[neural machine translation]] based methods, especially [[large language models]]) 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 criterion, choosing the translation which best keeps the goals. The
== Variants ==
| |||