Home / Curated / Algorithms / Simple recursive best-first search

Simple recursive best-first search

Algorithms AIMech:SimpleRecursiveBestFirstSearch DRAFT

Aliases: SRBFS

A recursive best-first search procedure that initializes generated children from their static evaluation values, explores the best child within an alternative-derived bound, and backs up returned values to decide which subtree to revisit.

Identity Notes & Concept Scope SRBFS is Korf’s simple recursive algorithm, not an alias for the full RBFS refinement. It resets regenerated children to their static values instead of conditionally inheriting a previously backed-up parent value. This distinction can cause additional regeneration. 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

Initialize each child’s stored value from its static evaluation and keep the children ordered by those values. Recurse into the best child with the smaller of the current bound and the next-best sibling’s value, then replace that child’s stored value with the returned value and reorder. Backtrack when the best available child exceeds the bound; a dead end returns infinity.

supports Source: Linear-Space Best-First Search: Summary of Results · Locator: Simple Recursive Best-First Search, printed pp. 534–535 / PDF pp. 2–3; SRBFS pseudocode and Figure 3

Scope #refinement-boundary

The full RBFS refinement preserves previously backed-up information when regenerating children. The paper distinguishes ordering all SRBFS expansions from ordering first-time RBFS expansions, because RBFS traverses previously expanded paths in depth-first order.

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

⚠️ Curated Limitations & Negative Results

Resetting regenerated child values can repeat already explored work before reaching a previously established frontier. Full RBFS adds a conditional inheritance rule to mitigate this.
Path cycles and termination require appropriate graph and evaluation assumptions or explicit path checks; the displayed procedure is not a complete production implementation for every graph.
The recursive representation retains the path and sibling alternatives. Linear-in-depth memory is conditional on bounded branching and fixed-size node information; it is not full-frontier storage.

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…
`full-refinement`	Linear-Space Best-First Search: Summary of Results Richard E. Korf	primary paper full_text	sha256:f30adb0c2776…

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/SimpleRecursiveBestFirstSearch.yaml