Home / Curated / Algorithms / Iterative-deepening A-star search

Iterative-deepening A-star search

Algorithms AIMech:IterativeDeepeningAStar DRAFT

Aliases: IDA*, Iterative-deepening-A*

A heuristic search algorithm that repeats depth-first passes bounded by f=g+h, starting with the start-state heuristic and raising each cutoff to the smallest value that exceeded the preceding cutoff.

Identity Notes & Concept Scope IDA-star is the cost-threshold variant of iterative deepening. The g value is the cost of the current search path and h estimates remaining cost. It does not maintain A-star’s complete open and closed lists, and its cutoff is not simply a depth limit. No normalized identity match was found across the 442 AIO and 119 prior native records; ignored-inclusive text hits in the main checkout were dependency-package documentation and an unrelated package-metadata substring, not existing concept records.

Claims & Grounded Evidence

2 Claims

Mechanism #search-procedure

Within each pass, expand along a depth-first path until g+h exceeds the current cutoff. Track the smallest exceeded value to set the next pass’s cutoff, then restart from the initial state; depth-first traversal state replaces the complete A-star frontier.

supports Source: Depth-First Iterative-Deepening: An Optimal Admissible Tree Search · Locator: Section 6, printed pp. 103–105 / PDF pp. 7–9; threshold update and qualified heuristic analysis

Limitation #regeneration-and-order

The later paper corroborates the minimum-exceeded-value threshold update and explains that iterative deepening need not follow best-first order with a nonmonotone cost function. It also identifies tree cases with many distinct costs in which regeneration overhead is substantial.

supports Source: Linear-Space Best-First Search: Summary of Results · Locator: Previous Work, printed pp. 533–534 / PDF pp. 1–2; Theoretical Results, printed p. 536 / PDF p. 4

⚠️ Curated Limitations & Negative Results

Lowest-cost solution arguments require an admissible heuristic and suitable search/termination assumptions; arbitrary heuristic estimates are not certified here.
The method regenerates search paths. Many distinct cutoff values or duplicate routes can impose substantial additional work; this record does not claim the same runtime or expansion count as A-star on every graph.
With a nonmonotone evaluation function, iterative deepening does not in general visit newly expanded nodes in best-first order within a cutoff.
The original journal paper has an access-limited 1986 erratum. Its basic procedure is corroborated by the 1992 primary paper; the 1985 global asymptotic-optimality theorem is not 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 119 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`	Depth-First Iterative-Deepening: An Optimal Admissible Tree Search Richard E. Korf	primary paper full_text	ID: doi:10.1016/0004-3702(85)90084-0 sha256:44fc92b6885a…
`later-primary-paper`	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:32:15Z

Updated: 2026-10-11T05:36:20Z

Source File: data/curated/IterativeDeepeningAStar.yaml