Home / Curated / Algorithms / Recursive best-first search

Recursive best-first search

Algorithms AIMech:RecursiveBestFirstSearch DRAFT

Aliases: RBFS

A recursive search algorithm that explores the best stored subtree alternative within an upper bound and conditionally passes a previously backed-up value to regenerated children, retaining path and sibling information instead of the full best-first frontier.

Identity Notes & Concept Scope RBFS denotes Korf’s full refinement of SRBFS. A backed-up value greater than the node’s static value signals previous exploration; only then do child values inherit the maximum of that backed-up value and their own static evaluations. Unconditionally replacing every child value by the maximum with its parent’s value would lose this distinction for nonmonotone evaluation functions. No normalized identity match was found across the 442 AIO and 124 prior native records; ignored-inclusive text hits in the main checkout were prior discovery leads, source citations and search-order contrasts, plus incidental dependency substrings, not existing concept records.

Claims & Grounded Evidence

2 Claims

Mechanism #search-procedure

For a node with static value f and stored value V, initialize each child from its static value unless V exceeds f, in which case use the maximum of V and the child’s static value. Recurse into the child with the smallest stored value using the smaller of the inherited bound and the next-best sibling value. Back up the returned value, reorder the children and switch subtrees when an alternative becomes preferable.

supports Source: Linear-Space Best-First Search: Summary of Results · Locator: Full Recursive Best-First Search, printed p. 535 / PDF p. 3; Theoretical Results, printed p. 536 / PDF p. 4

Mechanism #later-corroboration

The later primary paper reproduces the conditional inheritance rule and the bound obtained from competing stored subtree values before introducing separate re-expansion-control variants.

supports Source: Recursive Best-First Search with Bounded Overhead · Locator: Previous Work: Recursive Best-First Search and Figure 1, PDF p. 2

⚠️ Curated Limitations & Negative Results

The paper’s best-first-order statement concerns newly expanded search-tree nodes. Previously expanded paths may be regenerated in depth-first order.
Path and sibling storage is O(bd) for branching factor b and maximum depth d under the paper’s model; linear-in-depth storage assumes bounded b and fixed-size node data.
Numerous distinct evaluation values can cause substantial regeneration overhead. The memory saving does not establish an A-star-equivalent runtime bound.
If a cycle does not increase the evaluation value, explicit current-path cycle checking is needed to avoid looping; the method is not a global closed-list duplicate-elimination algorithm.

Artificial Intelligence Ontology (AIO) Grounding

Explicit AIO Snapshot Assessment: No Match

Rationale: No suitable AIO counterpart for this graph/state-space search procedure was identified in the inspected snapshot. Using graphs, evaluation functions or a search subroutine in an AI system does not equate the algorithm with a learned model, a learning task or a mathematical function.

Search Scope: All 442 pinned AIO labels and scoped synonyms and 124 preceding native identities were compared. Both updated checkouts were searched including hidden and ignored files. Exact CLASS nodes and edges for GraphLanguageModel, ReasoningLLM, NeuroSymbolicLLM, MachineLearningTask, MathematicalFunction and ReinforcementLearning were inspected, alongside semantic search for search, planning, heuristic, path, traversal, symbolic, reasoning and graph terminology.

Examined AIO Candidate	Rejection Reason
`AIO:GraphLanguageModel`	A language model operating on structured graph representations is not a graph traversal or shortest-path algorithm.
`AIO:ReasoningLLM`	Language-task deductive inference does not denote general state-space search.
`AIO:NeuroSymbolicLLM`	A language-model architecture combining neural and symbolic components is not the search procedure itself.
`AIO:MachineLearningTask`	Building methods that learn from data is not the identity of an algorithm traversing a specified graph.
`AIO:MathematicalFunction`	The search procedure is distinct from the mathematical functions it may evaluate.
`AIO:ReinforcementLearning`	A learning task balancing exploration and exploitation is distinct from deterministic graph/state-space traversal.

Evidence Sources & Primary Literature

2 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`method-source`	Linear-Space Best-First Search: Summary of Results Richard E. Korf	primary paper full_text	sha256:f30adb0c2776…
`later-primary-paper`	Recursive Best-First Search with Bounded Overhead Matthew Hatem, Scott Kiesel, Wheeler Ruml	primary paper full_text	ID: doi:10.1609/aaai.v29i1.9352 sha256:71550d1c85a5…

Curation Provenance

Curator: Codex

Method: ai_assisted

Model: GPT-6

Created: 2026-10-11T05:44:44Z

Updated: 2026-10-11T05:44:44Z

Source File: data/curated/RecursiveBestFirstSearch.yaml