From Wikipedia, the free encyclopedia
Jump to: navigation, search

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.


 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)
     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[edit]

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.


External links[edit]