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.