Iterative deepening A* (IDA*) is a graph traversal and path search algorithm that can find the shortest path between a designated start node and any member of a set of goal nodes in a weighted graph.

Unlike A*, IDA* does not utilize dynamic programming and therefore often ends up exploring the same nodes many times.

[1] Iterative-deepening-A* works as follows: at each iteration, perform a depth-first search, cutting off a branch when its total cost

This threshold starts at the estimate of the cost at the initial state, and increases for each iteration of the algorithm.

A* search keeps a large queue of unexplored nodes that can quickly fill up memory.

By contrast, because IDA* does not remember any node except the ones on the current path, it requires an amount of memory that is only linear in the length of the solution that it constructs.

Its time complexity is analyzed by Korf et al. under the assumption that the heuristic cost estimate h is consistent, meaning that for all nodes n and all neighbors n' of n; they conclude that compared to a brute-force tree search over an exponential-sized problem, IDA* achieves a smaller search depth (by a constant factor), but not a smaller branching factor.