Artificial Intelligence Stack Exchange is a question and answer site for people interested in conceptual questions about life and challenges in a world where "cognitive" functions can be mimicked in purely digital environment. It only takes a minute to sign up.
Sign up to join this community
The iterative deepening A* search is an algorithm that can find the shortest path between a designated start node and any member of a set of goals.
The A* algorithm evaluates nodes by combining the cost to reach the node and the cost to get from the node to the goal. How is iterative deepening A* better than the A* algorithm?
A* is a best-first search algorithm, which means that it is an algorithm that uses both "past knowledge", gathered while exploring the search space, denoted by $g(n)$, and an admissible heuristic function, denoted by $h(n)$, which estimates the distance to the goal node, for each node $n$. There are other best-first search algorithms, which differ only in the definition of their "evaluation function", denoted by $f(n)$. For example, the evaluation function of A* is $f(n) = g(n) + h(n)$, where $h$ is admissible.
A* is optimal, that is, it finds the optimal path between the starting and goal nodes or states. The optimality of A* is due to the use of an admissible heuristic function, which is a heuristic function which always underestimates the distance to the goal. A* is also complete, that is, it eventually finds this optimal path. However, the problem with A*, in many real-world situations, is that it has an exponential space complexity; more specifically, its space complexity is $\mathcal{O}(b^m)$, where $b$ is the (maximum) branching factor and $m$ is the maximum depth of the search tree. It also has a time complexity of $\mathcal{O}(b^m)$, but, in practice, it tends to find the solutions quite "fast" (for relatively small search spaces).
IDA* combines A* and IDDFS (or IDS). It does it "well", so it gets the advantages of both algorithms. It can be thought of as the IDDFS which uses, instead of the depth, the evaluation function $f(n) = g(n) + h(n)$ as the "cost threshold" or "cutoff". In the IDA* algorithm, a child $c$ of a node $n$ is added to the frontier (or fringe or border) if $f(c) < T$. This threshold $T$ is, at the beginning of the algorithm, the estimate of the distance to the goal from the starting node $s$, that is, $T = h(s)$. $T$ increases at each iteration of the algorithm (See the pseudocode of the IDA* algorithm for the details).
IDA* is also complete and optimal, but, as opposed to A*, it has a polynomial space complexity, more specifically, $\mathcal{O}(bd)$, where $b$ is the (maximum) branching factor and $d$ is the maximum depth fo the tree. IDA* still has an exponential time complexity of A*.
To conclude, IDA* has a better memory usage than A*. As in A* and unlike IDDFS, it concentrates on exploring the most promising nodes, and thus does not go to the same depth everywhere in the search tree (whereas ordinary IDDFS does). A* can be thought of as a dynamic programming algorithm. IDA* often ends up exploring the same nodes many times (as IDDFS), but, asymptotically, both A* and IDA* have the same exponential time complexity, that is, $\mathcal{O}(b^m)$.
So, which one is the best one? A* becomes impractical when the search space is huge, because of the memory constraints. So, in those cases, IDA* is definitely more appropriate. In general, IDA* is one of the very best optimal state space search techniques around. However, A* is conceptually simpler than IDA*. As a consequence, in practice, A* may be easier to implement than IDA*, but, in real-world scenarios, this is not really a problem, as they are both relatively easy to implement (anyway).
