2.3.10.1 IDA$^*$

Generalmente lo primero que se agota en A$^*$ es la memoria. Dos extensiones a A$^*$ tratan de reducir los requerimientos de memoria.

IDA$^*$, es una extensión natural de iteractive deepening. Se usa un límite de costo (más que de profundidad) iterativo.

IDA$^*$ es completo y óptimo como A$^*$, pero por ser depth-first, sólo requiere memoria proporcional al camino más largo que explora (aprox. $bd$, porqué depende del número de nodos por costo).

La complejidad de tiempo depende del número de valores que puede tomar la heurística.

Sin embargo, en problemas en donde la heurística cambia para cada estado (e.g., el TSP), lo que quiere decir es que cada contorno incluye sólo un estado. Si A$^*$ expande $N$ nodos, IDA$^*$ tendría que hacer $N$ iteraciones ( $1 + 2 + \ldots + N$), osea $O(N^2)$

Por lo que si $N$ es muy grande para ser guardada en memoria, seguramente $N^2$ es demasiado tiempo que se necesita esperar.