Breadth-first iterative-deepening A-star
Algorithms AIMech:BreadthFirstIDAStar DRAFT
Aliases: BFIDA*, Breadth-first iterative-deepening A*
An iterative-deepening heuristic graph-search algorithm that repeatedly runs breadth-first branch-and-bound within increasing hypothetical f=g+h cost bounds, beginning at the start-state f value, until a solution is found; the curated formulation uses unit edge costs and a nonnegative admissible heuristic with h(goal)=0.
Identity Notes & Concept Scope
BFIDA* changes the inner traversal of cost-contour iterative deepening to breadth-first branch-and-bound. It is distinct from depth-first IDA*, depth-limited iterative-deepening DFS, and a single BFBnB search with a supplied incumbent bound. The memory implementation can use frontier or layered duplicate handling. No normalized identity match was found across the 442 AIO and 135 prior native records; ignored-inclusive text hits in the main checkout were prior discovery leads, source citations, scope contrasts and DCBSS substring matches, plus seven public certificate-data substring matches, not existing concept records.
Claims & Grounded Evidence
2 Claims
Mechanism
#search-procedure
Set T=f(start). Run breadth-first branch-and-bound admitting nodes with f≤T. If no goal is reached, restart with a larger T, such as the least f value excluded on the preceding pass; the paper also describes increments of one in its unit-cost setting. Repeat until a solution is found. Breadth-first traversal, admissible pruning and sufficient resources preserve a minimum-cost solution in this uniform-cost setting.
Limitation
#analysis-conditions
The expansion-count theorems depend on growth assumptions, while breadth-first traversal restricts beneficial tie-breaking within a contour. Memory remains governed by the retained search frontier and duplicate-detection strategy.
⚠️ Curated Limitations & Negative Results
- The hypothetical threshold is inclusive. Reusing strict incumbent pruning at T=f(start) without a retained solution would be a different procedure.
- This method repeats breadth-first contours and retains frontier/duplicate information; it does not inherit the path-linear storage of depth-first IDA*.
- The asymptotic node-expansion analysis assumes exponential growth of distinct nodes per iteration; the directed-graph result additionally constrains solution depth relative to stored layers. It is not an unconditional wall-clock optimum.
- Large layers and tie contours can still be costly. Solvable finite-depth cases require sufficient memory; no universal termination guarantee on infinite unsolvable graphs is asserted.
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 135 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
|
Rong Zhou, Eric A. Hansen
|
primary paper
full_text
|
ID: doi:10.1016/j.artint.2005.12.002
sha256:9f094b2d1e98…
|
analysis-conditions
|
Rong Zhou, Eric A. Hansen
|
primary paper
full_text
|
ID: doi:10.1016/j.artint.2005.12.002
sha256:9f094b2d1e98…
|
Curation Provenance
Curator: Codex
Method: ai_assisted
Model: GPT-6
Created: 2026-10-11T06:16:04Z
Updated: 2026-10-11T06:17:28Z
Source File:
data/curated/BreadthFirstIDAStar.yaml