Iterative deepening A*
||This article may be too technical for most readers to understand. (November 2009)|
|Graph and tree
Iterative deepening A* (IDA*) is a graph traversal and path search algorithm that can find the shortest path between a designated start node and any member of a set of goal nodes in a weighted graph. It 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 a depth-first search algorithm, its memory usage is lower than in A*, but unlike ordinary iterative deepening 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 where is the cost to travel from the root to node and is a problem-specific heuristic estimate of the cost to travel from to the solution. As in A*, the heuristic has to have particular properties to guarantee optimality (shortest paths); see Properties, below.
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) step cost function is_goal(node) goal test successors(node) node expanding function procedure ida_star(root) 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
Like A*, IDA* is guaranteed to find the shortest path leading from the given start node to any goal node in the problem graph, if the heuristic function h is admissible, i.e.,
for all nodes n, where h* is the true cost of the shortest path from n to the nearest goal (the "perfect heuristic").:281
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. By contrast, because IDA* does not remember any node except the ones on the current path, it requires an amount of memory that is only 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
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.
- Bonet, Blai; Geffner, Héctor C. (2001). "Planning as heuristic search". Artificial Intelligence 129: 5. doi:10.1016/S0004-3702(01)00108-4.
- Korf, Richard (1985). "Depth-first Iterative-Deepening: An Optimal Admissible Tree Search" (PDF). Artificial Intelligence 27: 97–109. doi:10.1016/0004-3702(85)90084-0.
- Bratko, Ivan (2001). Prolog Programming for Artificial Intelligence. Pearson Education.
- 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.