A-star search
Algorithms AIMech:AStarSearch DRAFT
Aliases: A* search
A heuristic graph-search method that selects an open node using the sum of its best known path cost from the start and an estimated remaining cost to a goal.
Identity Notes & Concept Scope
This is the graph-search algorithm conventionally written A*, not a graph language model or a learned policy. Its heuristic estimate is distinct from the exact remaining path cost.
Claims & Grounded Evidence
1 Claim
Mechanism
#search-procedure
The procedure expands a minimum-score open node, updates successor path estimates, reopens a closed successor when a better estimate is found, and terminates when a selected node is a goal.
⚠️ Curated Limitations & Negative Results
- The original analysis assumes graph arc costs bounded below by a positive constant; its optimality arguments depend on heuristic and graph assumptions.
- This record curates the search mechanism, not a claim of fewest possible expansions or universal optimality. The 1972 correction and later optimal-efficiency analyses remain follow-up evidence.
Artificial Intelligence Ontology (AIO) Grounding
Explicit AIO Snapshot Assessment: No Match
Rationale: No suitable AIO counterpart was identified for heuristic path search. Shared use of graphs or the broad topic of reasoning does not establish a mapping to a language-model class.
Search Scope: Compared all 442 pinned AIO labels/scoped synonyms and 56 prior native identities; searched both checkouts including hidden and ignored files. Inspected candidate definitions including GraphLanguageModel, ReasoningLLM, NeuroSymbolicLLM, MachineLearningTask and MathematicalFunction.
| Examined AIO Candidate | Rejection Reason |
|---|---|
AIO:GraphLanguageModel
|
A language model over graph-structured inputs or outputs does not denote a heuristic graph-search algorithm; shared graph terminology is insufficient. |
AIO:ReasoningLLM
|
This class describes deductive inference during language tasks, not general graph path search. |
AIO:MathematicalFunction
|
The algorithm is a search procedure using an evaluation function, not that function itself. |
Evidence Sources & Primary Literature
1 Source| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
original-paper
|
Peter E. Hart, Nils J. Nilsson, Bertram Raphael
|
primary paper
full_text
|
ID: doi:10.1109/TSSC.1968.300136
sha256:ed435399010b…
|
Curation Provenance
Curator: Codex
Method: ai_assisted
Model: GPT-6
Created: 2026-10-11T03:36:55Z
Updated: 2026-10-11T03:36:55Z
Source File:
data/curated/AStarSearch.yaml