IDA*

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.

Applications of IDA* are found in such problems as planning.[2]

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.

Complexity[edit]

IDA* requires an amount of memory that is linear in the length of the solution that it constructs. Its time complexity is analyzed by Korf et al. under the assumption that the heuristic cost estimate h is consistent, meaning that h(x) \le \mathrm{cost}(n, n') + h(n') for all nodes n and all neighbors n' of n; they conclude that compared to a brute-force tree search over an exponential-sized problem, IDA* achieves a smaller search depth (by a constant factor), but not a smaller branching factor.[3]

References[edit]

  1. ^ Korf, Richard (1985). "Depth-first Iterative-Deepening: An Optimal Admissible Tree Search". Artificial Intelligence 27: 97–109. doi:10.1016/0004-3702(85)90084-0. 
  2. ^ Bonet, Blai; Geffner, Héctor C. (2001). "Planning as heuristic search". Artificial Intelligence 129: 5. doi:10.1016/S0004-3702(01)00108-4.  edit
  3. ^ Korf, Richard E.; Reid, Michael; Edelkamp, Stefan (2001). "Time complexity of iterative-deepening-A∗". Artificial Intelligence 129: 199. doi:10.1016/S0004-3702(01)00094-7.  edit

External links[edit]