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.
YouTube Encyclopedic
-
1/3Views:158 86155 24715 657
-
14. Depth-First Search (DFS), Topological Sort
-
Depth-first Search (DFS) on Graphs Part 2 - Implementation
-
Lecture 9 | Search 6: Iterative Deepening (IDS) and IDA*
Transcription
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
- ^ Zhou, Rong; Hansen, Eric A. (2005). "Beam-Stack Search: Integrating Backtracking with Beam Search" (PDF). CiteSeerx: 10.1.1.71.4147.
- ^ a b Furcy, David. Koenig, Sven. "Limited Discrepancy Beam Search". 2005. "Archived copy" (PDF). Retrieved 2007-12-22.
This page was last edited on 16 August 2023, at 11:04