Iterative-Deepening A* (IDA*) [Korf, 1985] performs a series of independent
depth-first searches, each with the cost-bound increased by the minimal amount.
Following the lines of the well-known A* heuristic search algorithm
[Pearl, 1985][Nilsson, 1980], the total cost 
of a node 
is
made up of the cost already spent in reaching that node 
,
plus a lower bound on the estimated cost of the path to a goal state 
.
At the beginning,
the cost bound is set to the heuristic estimate of the initial state, 
.
Then, for each iteration, the bound is increased to the minimum value
that exceeded the previous bound, as shown in the following pseudo code:
With an admissible (=non-overestimating) heuristic estimate function 
,
IDA* is guaranteed to find an optimal (shortest) solution path [Korf, 1985].
Moreover, IDA* obeys the same asymptotic branching factor as A* [Nilsson, 1980],
if the number of newly expanded nodes grows exponentially with the search depth
[Mahanti et al., 1992][Korf, 1985].
This growth rate, the heuristic branching factor,
depends on the average number of applicable operators per node
and the discrimination power of the heuristic estimate .