Richard Korf’s 1992 paper is a foundational contribution to heuristic search in Artificial Intelligence. It introduces Recursive Best-First Search (RBFS), an algorithm that resolves a long-standing trade-off: performing a "best-first" search without the exponential memory requirements that typically plague such methods.
The Memory-Optimality Dilemma
In the early 1990s, search algorithms faced a stark divide. Best-First Search (BFS), such as A*, is optimal in terms of node expansions but stores every encountered node in memory. This leads to exponential memory growth, often exhausting system resources in minutes on complex problems.
Iterative Deepening (IDA*) was the standard memory-efficient alternative, using a depth-first approach to maintain linear space complexity. However, IDA requires a "monotonic" cost function—where path costs never decrease—to maintain its efficiency. In many practical scenarios, such as weighted searches used to find sub-optimal solutions quickly, cost functions are non-monotonic. In these cases, IDA loses its best-first property and becomes highly inefficient. RBFS was designed to be both memory-efficient and strictly best-first, regardless of the cost function's monotonicity.
Methodology: From SRBFS to RBFS
Korf developed the algorithm in two stages:
- Simple Recursive Best-First Search (SRBFS): This version uses a local cost threshold for each recursive call. When the search down a specific branch exceeds the cost of the best available alternative (a sibling node), the recursion backtracks. Before "forgetting" the explored subtree to save memory, it "backs up" the minimum cost found and stores it at the parent node.
- Recursive Best-First Search (RBFS): The refined version introduces value inheritance. If a parent node has a higher stored value than its children (due to a previous search), the children inherit that higher value. This prevents the algorithm from repeatedly re-exploring shallow, low-cost nodes that have already been proven to lead to high-cost subtrees.
Unlike A*, which maintains a massive global list of nodes, RBFS only keeps the current path and the immediate siblings of nodes on that path in the recursion stack.
Key Results and Performance
The algorithm was evaluated on classic combinatorial problems, including the Traveling Salesman Problem (TSP) and various sliding tile puzzles (8, 15, and 24-puzzles).
- Space Complexity: RBFS achieves $O(bd)$ space complexity (where $b$ is the branching factor and $d$ is depth), a massive improvement over the $O(b^d)$ required by standard Best-First Search.
- Efficiency in Weighted Search: In tests on the 15-puzzle and 24-puzzle using weighted heuristics, RBFS consistently found shorter solutions than Weighted IDA (WIDA). Because RBFS maintains a strict best-first order, it avoids the inefficiencies IDA* encounters with non-monotonic functions.
- Node Generation: On the TSP, RBFS generated only one-sixth as many nodes as IDA* to find optimal solutions.
While RBFS is approximately 29% slower per node generation than WIDA due to recursive overhead, it remains faster than A because it avoids the computational cost of sorting and maintaining a massive "Open" list.
Insights and Limitations
Korf’s work demonstrates that "Best-First" describes an expansion order, not a storage requirement. By carefully backing up values, a local recursion stack can simulate a global search order. The primary trade-off is node regeneration: RBFS must re-expand nodes it has previously "forgotten." In the worst-case scenario, where every node has a unique cost, time complexity can reach $O(b^{2d})$.
Furthermore, the efficiency of RBFS relies on "clustering," where nodes of similar costs are grouped together in the tree. If costs are distributed randomly, the algorithm may "flutter" excessively between branches. Despite these limitations, RBFS remains a landmark algorithm for solving large-scale search problems on systems with limited memory.
Summary updated