How is interactive deepening a* better than a*?

Interactive deepening 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 O(bm), where b is the (maximum) branching factor and m is the maximum depth of the search tree. It also has a time complexity of O(bm), 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)

IDA* is also complete and optimal, but, as opposed to A*It has a polynomial space complexity, more specifically, O(bd), where b is the (maximum) branching factor and d is the maximum depth of 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, O(bm).

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).