|Graph and tree
IDA* 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 where is the cost to travel from the root to node and is the heuristic estimate of the cost to travel from to the solution.
The code is based on.
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.
- Korf, Richard (1985). "Depth-first Iterative-Deepening: An Optimal Admissible Tree Search". Artificial Intelligence 27: 97–109.
- Lecture Notes: IDA*