Overview
IDA* performs depth-first searches bounded by f-cost, increasing the bound until it reaches a goal, which is useful in puzzle and state-space searches.
CoreSource checked
IDA*
Combines A* scoring with iterative deepening to search with lower memory use.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Pathfinding
- Difficulty
- Advanced
- Family
- Heuristic Search
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 2
- Relationships
- 4
- Code example
- Ready
- Visualization
- Ready
- Aliases
- Iterative Deepening A*, IDA star
Core Concepts
f-cost bounddepth-first searchadmissible heuristiciterative deepening
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(b^d)
Average
O(b^d)
Worst
O(b^d)
Space
O(d)
When to Use
- Use when route planning needs f-cost bound.
- Use when the input matches the assumptions behind heuristic Search.
When Not to Use
- Avoid when edge costs or movement rules change faster than the search can update them.
- Avoid when a simpler algorithm gives the required result with less setup.
What It Does
- Combines A* scoring with iterative deepening to search with lower memory use
- Uses f-cost bound and depth-first search to guide the work.
- Produces path.
Use Cases
- Route planning
- Game navigation
- Robotics motion planning
Inputs
- Search graph or state space
- Start state
- Goal state or target set
Outputs
- Path
- Distance estimate
- Search frontier state
Key Formulas (2)
A* priority
f(n) = g(n) + h(n)
f(n) = g(n) + h(n)Combines known path cost and an estimated remaining cost.
Bound update
boundnext = min(f(n) > bound)
bound_next = min(f(n) > bound)Chooses the next search bound from deferred nodes.
Pseudocode
- 1.Prepare the inputs and state needed for IDA*.
- 2.Apply the f-cost bound step while the stopping condition has not been met.
- 3.Update intermediate state and discard invalid candidates.
- 4.Return path.
Canonical Example
- Input
- sliding puzzle state, goal state, Manhattan-distance heuristic
- Output
- shortest move sequence if the heuristic is admissible
- Explanation
- IDA* repeats depth-first searches with increasing f-cost thresholds until a solution is found.
Implementation Notes
- Use f = g + h as the depth-first search cutoff.
- Return the smallest exceeded f-cost as the next threshold.
- Track the current path to avoid immediate cycles.
Common Pitfalls
- Using a non-admissible heuristic while expecting optimal paths.
- Failing to carry the next larger threshold back from a failed iteration.
- Letting repeated states cause excessive search without cycle checks.
Interactive Mechanism Walkthrough
2D Grid Wavefront & TrajectoryShow the frontier, settled nodes, and the final path over the search space.
S
#
#
#
#
#
#
#
G
Step 1 of 4: Prepare the inputs and state needed for IDA*.
pathfinding-mechanismNotes
IDA* should be used with the assumptions and tradeoffs of heuristic Search in mind.
Sources (2)
What each reference supports for this entry.
Artificial Intelligence: A Modern Approach
BookAI search reference covering IDA* heuristic evaluation, frontier ordering, optimality conditions, or memory tradeoffs.
Open sourceKorf IDA*
PaperOriginal IDA* reference for depth-first iterative-deepening with admissible heuristic thresholds.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Variant ofA* Search
Pathfinding · Core
IDA* uses iterative deepening with an A*-style cost bound.
Compare with thisAlternativesFringe Search
Pathfinding · Extended
Fringe search and IDA* are memory-conscious heuristic searches that advance cost thresholds.
Compare with thisRelationships
View full relationship pageVariant ofA* Search
IDA* uses iterative deepening with an A*-style cost bound.
IDA* combines heuristic bounds with iterative deepening depth-first search.
Related Algorithms
Tags
PathfindingHeuristic SearchIterativeDepth First Search