# IDA*

IDA*[1] is a variant of iterative deepening depth-first search that borrows the idea to use a heuristic function to evaluate the remaining cost to get to the goal from the A* search algorithm. Since it is based on iterative deepening depth-first search, its memory usage is lower than in A*, but unlike ordinary iterative deepening depth-first search, it concentrates on exploring the most promising nodes and thus doesn't go to the same depth everywhere in the search tree. Unlike A*, IDA* doesn't utilize dynamic programming and therefore often ends up exploring the same nodes many times.

While the standard iterative deepening depth-first search uses search depth as the cutoff for each iteration, the IDA* uses the more informative $f(n) = g(n) + h(n)$ where $g(n)$ is the cost to travel from the root to node $n$ and $h(n)$ is the heuristic estimate of the cost to travel from $n$ to the solution.

## Pseudocode

 node              current node
g                 the cost to reach current node
f                 estimated cost of the cheapest path (root..node..goal)
h(node)           estimated cost of the cheapest path (node..goal)
cost(node, succ)  path cost function
is_goal(node)     goal test
successors(node)  node expanding function

procedure ida_star(root, cost(), is_goal(), h())
bound := h(root)
loop
t := search(root, 0, bound)
if t = FOUND then return FOUND
if t = ∞ then return NOT_FOUND
bound := t
end loop
end procedure

function search(node, g, bound)
f := g + h(node)
if f > bound then return f
if is_goal(node) then return FOUND
min := ∞
for succ in successors(node) do
t := search(succ, g + cost(node, succ), bound)
if t = FOUND then return FOUND
if t < min then min := t
end for
return min
end function


## Comparison to other algorithms

The A* search is one of the best general-purpose graph search algorithms when there's a way to estimate the distance to the goal. IDA* is slightly slower than A* (it explores the same nodes multiple times because it doesn't remember prior work) but is beneficial when the problem is memory constrained. A* search keeps a large queue of unexplored nodes that can quickly fill up memory. Because IDA* does not remember any node except the ones on the current path it has an extremely small memory profile.