Beam Search

In computer science, beam search is a 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 which attempts to predict how close a partial solution is to a complete solution (goal state). But in beam search, only a predetermined number of best partial solutions are kept as candidates.

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, sorting them in increasing order of heuristic cost. However, it only stores a predetermined number 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) and optimality (the guarantee that it will find the best solution).

The beam width can either be fixed or variable. One approach that uses a variable beam width starts with the width at a minimum. If no solution is found, the beam is widened and the procedure is repeated.

Read more about Beam Search:  Name, Uses, Extensions

Other articles related to "beam search, search, beam":

Beam Search - Extensions
... Beam search has been made complete by combining it with depth-first search, resulting in Beam Stack Search and Depth-First Beam Search, and limited ... The resulting search algorithms are anytime algorithms that find good but likely sub-optimal solutions quickly, like beam search, then backtrack and ...
Beam Stack Search
... Beam Stack Search is a search algorithm that combines chronological backtracking (that is, depth-first search) with beam search and is similar to Depth-First Beam Search ... Both search algorithms are anytime algorithms that find good but likely sub-optimal solutions quickly, like beam search, then backtrack and continue to find improved solutions until ...

Famous quotes containing the words search and/or beam:

    You will never be happy if you continue to search for what happiness consists of. You will never live if you are looking for the meaning of life.
    Albert Camus (1913–1960)

    It was at that moment, just after Krug had fallen through the bottom of a confused dream and sat up on the straw with a gasp—and just before his reality, his remembered hideous misfortune could pounce upon him—it was then that I felt a pang of pity for Adam and slid towards him along an inclined beam of pale light—causing instantaneous madness, but at least saving him from the senseless agony of his logical fate.
    Vladimir Nabokov (1899–1977)