*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 .

Mon Dec 19 17:27:56 MET 1994