beam stack search
Beam stack search{{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 }} is a search algorithm that combines chronological backtracking (that is, depth-first search) with beam search and is similar to depth-first beam search.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 }} Both search algorithms are anytime algorithms 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 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.
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 backtracking, which often outperforms the chronological backtracking done by beam stack search and depth-first beam search.