# recursive best-first search

> search algorithm

**Wikidata**: [Q12072154](https://www.wikidata.org/wiki/Q12072154)  
**Source**: https://4ort.xyz/entity/recursive-best-first-search

## Summary
Recursive best-first search (RBFS) is an informed search algorithm and pathfinding algorithm invented by American computer scientist Richard E. Korf in 1992. It is designed as a linear-space best-first search that functions as a recursive subclass of the A* search algorithm.

## Key Facts
- **Inventor**: Richard E. Korf, an American computer scientist.
- **Year of Invention**: 1992.
- **Algorithm Type**: Informed search algorithm and pathfinding algorithm.
- **Acronym**: RBFS.
- **Parent Class**: Subclass of the A* search algorithm.
- **Naming**: Named after the best-first search method.
- **Academic Source**: Described in *Artificial Intelligence: A Modern Approach* (pages 99–101).
- **Key Characteristic**: A linear-space best-first search.
- **Google Knowledge Graph ID**: /g/15dpdkpg.

## FAQs
### Q: Who created recursive best-first search?
A: Recursive best-first search was created by Richard E. Korf, an American computer scientist, in 1992.

### Q: What type of algorithm is recursive best-first search?
A: It is an informed search algorithm used for pathfinding and graph traversal. It is specifically classified as a linear-space best-first search.

### Q: How is recursive best-first search related to A*?
A: RBFS is a subclass of the A* search algorithm. It is designed to behave like A* but operates using linear memory space.

## Why It Matters
Recursive best-first search (RBFS) is significant in the field of artificial intelligence and computer science because it addresses the memory limitations found in standard best-first search algorithms like A*. While A* is optimal, it often requires exponential memory to store the search tree, which makes it infeasible for complex, large-scale problems. RBFS matters because it is a "linear-space" algorithm, meaning it drastically reduces the memory required to perform the search.

By utilizing a recursive approach, RBFS mimics the behavior of a standard best-first search without retaining the entire frontier of nodes in memory. This allows it to solve problems that would otherwise exceed the memory capacity of standard heuristic searches. Its inclusion in the seminal textbook *Artificial Intelligence: A Modern Approach* underscores its status as a foundational technique for efficient pathfinding in constrained environments.

## Notable For
-   Being a **linear-space** alternative to A* search.
-   Invention by **Richard E. Korf**, a prominent figure in heuristic search.
-   Serving as a **subclass of the A* search algorithm**.
-   Detailed coverage in the standard AI textbook ***Artificial Intelligence: A Modern Approach***.
-   Being an **informed search algorithm**, utilizing preliminary heuristic information.

## Body
### Identity and Classification
Recursive best-first search (RBFS) is a pathfinding and graph traversal algorithm. It is formally classified as an informed search algorithm, implying it utilizes heuristic information to guide its search process. It operates as a specific implementation or subclass of the A* search algorithm.

### Historical Context
The algorithm was discovered or invented by Richard E. Korf in 1992. Korf, an American computer scientist born in 1956, is credited with the development of this method as detailed in the work "Linear-Space Best-First Search: Summary of Results."

### Technical Characteristics
RBFS is distinct for its memory efficiency. It is categorized explicitly as a "Linear-space best-first search." Unlike standard best-first searches which may keep all generated nodes in memory, RBFS is structured to operate within linear space constraints relative to the depth of the search.

### Academic Documentation
The algorithm is a standard topic in artificial intelligence education. It is described by the source "Artificial Intelligence: A Modern Approach," specifically appearing on pages 99 through 101. It has Wikidata entries in multiple languages, including Italian, Russian, and Ukrainian.

## References

1. Linear-Space Best-First Search: Summary of Results