CS & AI Student | Aspiring Software Developer | Passion for ML and Wolfram
When classic search methods like A* become impractical, either due to memory limits or massive search spaces, you can turn to more advanced variants that. These algorithms can:
In this lesson, we will look at five advanced search techniques:
When one thinks of an "advanced" search algorithm, one might think of a single algorithm that has a really large number of steps, or steps that are very complicated. This is almost always not the case. The "advanced" nature of these algorithms comes from the fact that they combine the advantages of multiple algorithms. Most of these algorithms are some variant of A* search, and for good reason: A* search is optimal if the heuristic is engineered properly. Given this property, it is only natural to combine it with efficiency techniques, such as iterative deepening or memory-bounding, to maintain the accuracy of the search whilst improving time and memory efficiency. This is especially important for large search spaces, where even informed search algorithms like A* can become intractable.
Iterative Deepening A* (IDA*) is a memory-efficient variant of A* that combines heuristic-guided search with iterative deepening (a technique mentioned briefly in Section 1, where we progressively increase the depth limit).
Rather than tracking all frontier nodes, it performs depth-first searches with an increasing threshold on the cost function: f(n) = g(n) + h(n).
The threshold begins at h(start) and increments to the minimum exceeded cost each iteration.
Recursive Best-First Search (RBFS) is an informed search that mimics A* but within linear memory by using recursion and backtracking. It keeps track only of the current path and the best alternative f-values when exceeding a bound.
Simplified Memory-Bounded A* (SMA*) is a memory-limited adaptation of A*. It uses normal A* search with OPEN and CLOSED lists, but prunes nodes when memory is exhausted by discarding the highest-cost leaf node and remembering its cost for potential regeneration later.
A common option in hyperparameter optimisation, beam search is a best-first heuristic search that, instead of keeping all frontier nodes, only retains a fixed number (beam width, β) of the most promising nodes per level. It continues expanding successors within this beam limit.
Closely related is Local Beam Search, a local-search variant of beam search. It starts with k randomly chosen states (candidate solutions), generates all their neighbors, and selects the top k best among them for the next iteration, repeating until convergence.
Tabu Search is a heuristic search method that uses a list of "forbidden" moves to guide the search. By using the memory of recent states (a tabu list) to avoid immediate revisits whilst allowing some worsening moves to escape local maxima or plateaus, Tabu Search can find a good middle ground between exploration and exploitation. It is conceptually a combination of A* and Hill Climbing.
My goal with this section was to demonstrate that there is no single "advanced" algorithm that will work the best in practice for any problem. In fact, I would argue the opposite: the more advanced we make an algorithm, the more specialized it becomes. I encourage you, the reader, to think of you knowledge as a toolbox of search techniques, not algorithms. When you encounter a search problem that cannot be solved with uninformed/informed search techniques, think about what techniques you know, what properties you want your search algorithm to have, and how we can combine them for optimal efficiency to solve the specific problem.