Beam stack search

Beam Stack Search[1] is a search algorithm that combines chronological backtracking (that is, depth-first search) with beam search and is similar to Depth-First Beam Search.[2] 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[2] (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.

References

  1. ↑ Zhou, Rong; Hansen, Eric (2005). "Beam-Stack Search: Integrating Backtracking with Beam Search". CiteSeerX 10.1.1.71.4147Freely accessible.
  2. 1 2 Furcy, David. Koenig, Sven. "Limited Discrepancy Beam Search". 2005. "Archived copy" (PDF). Archived from the original (PDF) on 2008-05-16. Retrieved 2007-12-22.


This article is issued from Wikipedia - version of the 11/10/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.