Best-first search
Algorithms AIMech:BestFirstSearch DRAFT
A search strategy that repeatedly expands the open node with the best value under a specified evaluation rule, adding eligible successors to the open frontier.
Identity Notes & Concept Scope
This record describes the canonical global minimum-f form, with lower values defined as better. A-star, heuristic-only greedy best-first search and weighted A-star choose different evaluation rules. Broader literature also calls restricted-candidate-set policies best-first; their extra selection rules are not part of this core procedure. BFS is not an alias here because it identifies breadth-first search in AIMech. 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
Maintain an open frontier of generated nodes eligible for expansion. Select a node with minimum evaluation value, test the selected node for a goal, and otherwise expand it and update the frontier under the chosen duplicate policy. The evaluation rule and duplicate handling determine the specific search algorithm.
Scope
#family-boundary
Global frontier selection differs from choosing only a current node’s neighbor or discarding nodes to enforce a beam width. Some named best-first variants additionally restrict selection to a privileged subset of the frontier.
⚠️ Curated Limitations & Negative Results
- A minimum evaluation value alone does not guarantee minimum solution cost; the meaning and assumptions of the evaluation rule matter.
- Maintaining the full frontier and explored-state information can require substantial memory. Recursive or bounded-memory variants change what is retained.
- Tie-breaking, duplicate updates and termination conditions are additional algorithm choices; the generic strategy does not settle them or guarantee completion on an infinite space.
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
|
Richard E. Korf
|
primary paper
full_text
|
sha256:f30adb0c2776…
|
comparison-paper
|
Christopher Wilt, Jordan Thayer, Wheeler Ruml
|
primary paper
full_text
|
ID: doi:10.1609/socs.v1i1.18182
sha256:cfc3cf8f422b…
|
Curation Provenance
Curator: Codex
Method: ai_assisted
Model: GPT-6
Created: 2026-10-11T05:44:44Z
Updated: 2026-10-11T05:44:56Z
Source File:
data/curated/BestFirstSearch.yaml