IDA*

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

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

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

References[edit]

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

External links[edit]