Beam stack search: Difference between revisions

Revision as of 08:02, 21 November 2005

Latest revision as of 11:04, 16 August 2023

(34 intermediate revisions by 30 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, Mississippi State during the 15th International Conference on Automated Planning and Scheduling , Monterey, CA.

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.

The following web page has the original paper submitted by Zhou and Hansen.

http://www.cs.msstate.edu/~hansen/papers/icaps05beam.pdf

== References ==

{{reflist}}

{{DEFAULTSORT:Beam Stack Search}}

[[Category:Search algorithms]]