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.

gollark: Wait, if the file-last-edited thing returns real-world unix tme, couldn't you just edit a file and check the timestamp on it?
gollark: Do `tyre.getReactionStats()` instead of `tyre.getReactionStats`.
gollark: You're unpacking a function. You need to actually call it.
gollark: The OC-specific docs are here but they're kind of bad: https://ocdoc.cil.li/
gollark: It's not a *video*, but you can read the PIL manual for Lua here: https://www.lua.org/pil/contents.html - it doesn't cover OC-specific stuff but it's good to know.

References
  1. Zhou, Rong; Hansen, Eric (2005). "Beam-Stack Search: Integrating Backtracking with Beam Search". CiteSeerX 10.1.1.71.4147. Cite journal requires |journal= (help)
  2. Furcy, David. Koenig, Sven. "Limited Discrepancy Beam Search". 2005. "Archived copy" (PDF). Retrieved 2007-12-22.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.