Beam stack search: Difference between revisions

Revision as of 22:31, 23 November 2005

Latest revision as of 11:04, 16 August 2023

(31 intermediate revisions by 27 users not shown)

Line 1:

'''Beam stack search'''<ref>{{cite web|url=https://cdn.aaai.org/ICAPS/2005/ICAPS05-010.pdf | last1 = Zhou | first1 = Rong | last2 = Hansen | first2 = Eric A. | title = Beam-Stack Search: Integrating Backtracking with Beam Search |id={{CiteSeerX|10.1.1.71.4147}} | year = 2005 }}</ref> is a [[search algorithm]] that combines chronological [[backtracking]] (that is, [[depth-first search]]) with [[beam search]] and is similar to depth-first beam search.<ref name="furcy">Furcy, David. Koenig, Sven. "Limited Discrepancy Beam Search". 2005. {{cite web|url=http://www.ijcai.org/papers/0596.pdf |title=Archived copy |accessdate=2007-12-22 }}</ref> 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.

'''Beam stack search''' is a search [[algorithm]] which integrates backtracking with [[beam search]].

== Implementation ==

This search algorithm was put forward 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]].

Beam stack search uses the beam stack as a [[data structure]] 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.

It could be describes 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.

== Alternatives ==

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

Beam search using limited discrepancy backtracking<ref name="furcy" /> (BULB) is a search algorithm that combines limited discrepancy search with beam search and thus performs non-chronological [[backtracking]], which often outperforms the chronological backtracking done by beam stack search and depth-first beam search.

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

==External linkReferences ==

{{reflist}}

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

{{DEFAULTSORT:Beam Stack Search}}

{{compu-stub}}

[[Category:Search algorithms]]