# IDA*

IDA*[1] is a variant of the A* search algorithm which uses iterative deepening to keep the memory usage lower than in A*. It is an informed search based on the idea of the uninformed iterative deepening depth-first search.

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.

## References

1. ^ Korf, Richard (1985). "Depth-first Iterative-Deepening: An Optimal Admissible Tree Search". Artificial Intelligence 27: 97–109.