Beam stack search

Beam stack search

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 on Automated Planning and Scheduling in Monterey, California.

It could be described as a method for transforming beam search into a complete search algorithm that is guaranteed to find an optimal solution. It uses a new data structure, called a beam stack, that makes it possible to integrate systematic backtracking with beam search.

The resulting search algorithm is an anytime algorithm that finds a good, sub-optimal solution quickly, like beam search, then backtracks and continues to find improved solutions until convergence to an optimal solution.

In most respects, the divide and conquer algorithm technique can be combined with beam-stack search in the same way as with beam search, creating an algorithm called divide-and-conquer beam-stack search.

External links

* [http://www.cs.msstate.edu/~hansen/papers/icaps05beam.pdf Zhou and Hansen's original paper]


Wikimedia Foundation. 2010.

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

Look at other dictionaries:

  • 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

  • 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… …   Wikipedia

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

  • Depth-limited search — Class Search Algorithm Data structure Graph Worst case performance O( | V | + | E | ) …   Wikipedia

  • Algorithme de recherche en faisceau — En informatique, la recherche en faisceau est un algorithme de recherche heuristique qui explore un graphe en ne considérant qu un ensemble limité de fils de chaque nœud. La recherche en faisceau est une optimisation de l algorithme de parcours… …   Wikipédia en Français

  • Mathematics and Physical Sciences — ▪ 2003 Introduction Mathematics       Mathematics in 2002 was marked by two discoveries in number theory. The first may have practical implications; the second satisfied a 150 year old curiosity.       Computer scientist Manindra Agrawal of the… …   Universalium

  • Tree traversal — Graph and tree search algorithms Alpha beta pruning A* B* Beam Bellman–Ford algorithm Best first Bidirectional …   Wikipedia

  • architecture — /ahr ki tek cheuhr/, n. 1. the profession of designing buildings, open areas, communities, and other artificial constructions and environments, usually with some regard to aesthetic effect. Architecture often includes design or selection of… …   Universalium

  • Superlens — A superlens, super lens or perfect lens is a lens which uses metamaterials to go beyond the diffraction limit. The diffraction limit is an inherent limitation in conventional optical devices or lenses.[1] In 2000, a type of lens was proposed,… …   Wikipedia

  • Marshall Amplification — Industry Amplification, Musical Instrument Manufacturing Founded London, United Kingdom (1960) Founder(s) J …   Wikipedia

Share the article and excerpts

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