Beam stack search is a

search algorithm In computer science, a search algorithm is an algorithm designed to solve a search problem. Search algorithms work to retrieve information stored within particular data structure, or calculated in the Feasible region, search space of a problem do ...

that combines chronological

backtracking Backtracking is a class of algorithms for finding solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it de ...

(that is,

depth-first search Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible alo ...

) with

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 sea ...

and is similar to depth-first beam search.Furcy, David. Koenig, Sven. "Limited Discrepancy Beam Search". 2005. Both search algorithms are

anytime algorithm In computer science, an anytime algorithm is an algorithm that can return a valid solution to a problem even if it is interrupted before it ends. The algorithm is expected to find better and better solutions the longer it keeps running. Most algor ...

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 structure In computer science, a data structure is a data organization, management, and storage format that is usually chosen for Efficiency, efficient Data access, access to data. More precisely, a data structure is a collection of data values, the rel ...

to integrate chronological backtracking with beam search and can be combined with the

divide and conquer algorithm In computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical ...

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

, which often outperforms the chronological backtracking done by beam stack search and depth-first beam search.

References

{{DEFAULTSORT:Beam Stack Search Search algorithms