Iterative deepening A*

Iterative deepening A*

Class	Search algorithm
Data structure	Tree, Graph
Worst-case space complexity	${\displaystyle O(d)}$

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 conservatively estimate 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 does not go to the same depth everywhere in the search tree. Unlike A*, IDA* does not 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 ${\displaystyle f(n)=g(n)+h(n)}$, where ${\displaystyle g(n)}$ is the cost to travel from the root to node ${\displaystyle n}$ and ${\displaystyle h(n)}$ is a problem-specific heuristic estimate of the cost to travel from ${\displaystyle n}$ to the goal.

The algorithm was first described by Richard Korf in 1985.^[1]