Beam stack search
Encyclopedia
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 algorithm
s that find good but likely sub-optimal solutions quickly, like beam search, then backtrack and continue to find improved solutions until convergence to an optimal solution.
to integrate chronological backtracking with beam search and can be combined with the divide and conquer algorithm
technique, resulting in divide-and-conquer beam-stack search.
, which often outperforms the chronological backtracking done by Beam Stack Search and Depth-First Beam Search.
Search algorithm
In computer science, a search algorithm is an algorithm for finding an item with specified properties among a collection of items. The items may be stored individually as records in a database; or may be elements of a search space defined by a mathematical formula or procedure, such as the roots...
that combines chronological backtracking
Backtracking
Backtracking is a general algorithm for finding all solutions to some computational problem, that incrementally builds candidates to the solutions, and abandons each partial candidate c as soon as it determines that c cannot possibly be completed to a valid solution.The classic textbook example...
(that is, depth-first search
Depth-first search
Depth-first search is an algorithm for traversing or searching a tree, tree structure, or graph. One starts at the root and explores as far as possible along each branch before backtracking....
) with beam search
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...
and is similar to Depth-First Beam Search. Both search algorithms are anytime algorithm
Anytime algorithm
In computer science an anytime algorithm is an algorithm that can return a valid solution to a problem even if it's interrupted at any time before it ends. The algorithm is expected to find better and better solutions the more time it keeps running....
s that find good but likely sub-optimal solutions quickly, like beam search, then backtrack and continue to find improved solutions until convergence to an optimal solution.
Implementation
Beam Stack Search uses the beam stack as a data structureData structure
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
to integrate chronological backtracking with beam search and can be combined with the divide and conquer algorithm
Divide and conquer algorithm
In computer science, divide and conquer is an important algorithm design paradigm based on multi-branched recursion. A divide and conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same type, until these become simple enough to be solved directly...
technique, resulting in divide-and-conquer beam-stack search.
Alternatives
Beam Search Using Limited Discrepancy Backtracking (BULB) is a search algorithm that combines limited discrepancy search with beam search and thus performs non-chronological backtrackingBacktracking
Backtracking is a general algorithm for finding all solutions to some computational problem, that incrementally builds candidates to the solutions, and abandons each partial candidate c as soon as it determines that c cannot possibly be completed to a valid solution.The classic textbook example...
, which often outperforms the chronological backtracking done by Beam Stack Search and Depth-First Beam Search.