Hoy vamos a presentar una variante del algoritmo "A estrella" que reduce significativamente los recursos computacionales, en particular, los de memoria. El algoritmo se denomina "algoritmo A* de profundidad iterada" o "IDA*". El algoritmo ID invoca de manera iterada el algoritmo DLS incrementando, con cada iteración, la cota de profundidad. Recordemos que el algoritmo ID consume tan sólo "o", "b" por "d" en memoria y que además nos regresa a la solución óptima. Estas características las vamos a tener también en el algoritmo que vamos a presentar hoy. A diferencia del algoritmo ID, donde tenemos una cota de profundidad, el algoritmo IDA* va a tener una cota de costo. La cota se incrementará de manera automática si es que una solución no se encuentra dentro de la restricción de la cota actual. Vamos a presentar el algoritmo IDA*. La versión que vamos a ver aquí es una versión iterativa, el algoritmo generalmente se presenta con una versión recursiva. Las entradas del algoritmo son las mismas que teníamos para el algoritmo A*. Vamos a tener nuestro estado inicial, "S cero". Vamos a tener nuestra función de paro, la función de costo de arista y la heurística. El primer paso del algoritmo va a ser establecer la cota con la que va a trabajar el algoritmo. Esta cota va a ser igual a la heurística del nodo inicial. La cota la denominamos como "C", entonces, "C" es igual a "h" de "S cero". Lo siguiente, vamos a entrar a un ciclo, no sabemos cuánto va a durar, entonces, vamos a ponerlo como "while", se va a repetir un número indeterminado de pasos. Dentro de este ciclo vamos a ir aumentando paulatinamente nuestra cota de costo hasta encontrar la solución. Nuestro primer paso dentro de este ciclo es inicializar nuestras estructuras de datos. Vamos a inicializar agenda con el valor de "S cero", entonces, lo ponemos así: "Agenda.push(S0)". También, vamos a necesitar una variable denominada "mínimo", que nos va a servir para calcular la cota siguiente. A esta le vamos a establecer un valor muy alto, en este caso, infinito. Y vamos a tener un conjunto donde vamos a ir revisando los nodos que están en la ruta, a este conjunto lo vamos a denominar "X", que aquí se va a inicializar como vacío. Una vez que inicializamos nuestras estructuras de datos, ahora sí vamos a empezar a iterar sobre los elementos que están en la agenda. Hacemos un nuevo "while". Mientras la agenda tenga elementos, vamos a repetir los siguientes pasos. Primero, vamos a inspeccionar cuál es el elemento que está en el tope de la pila, nuestra pila es la agenda. Pero, no vamos a extraerlo, simplemente vamos a ver cuál es. A ese elemento le vamos a denominar "n". Voy a indicar esa operación como "peek". "Peek", a diferencia de "pop", no extrae el elemento, simplemente nos da una referencia al mismo. Ya tenemos "n". Vamos a verificar si ya termin mos, con la condición de paro. Si se cumple la condición de paro, vamos a regresar la ruta. Si no se cumple la condición de paro, lo siguiente es verificar si "n" está en la ruta. Nos va a interesar que no esté. Si "n" no está en "X", entonces, vamos a proceder como sigue. Agregamos a "X", "n". Lo siguiente es obtener los sucesores de nuestro nodo "n". Recordemos que la función "f" es la misma que utiliza A* y es la suma del costo acumulado "g" de "n", más el valor de la heurística o valor estimado a la meta. Entonces, "f(n) = g(n) + h(n)". Vamos a utilizar esta función "f" para ordenar los sucesores, entonces, lo indicamos de esta forma: "sucesores" va a hacer una lista de estados ordenada por la función "f", entonces, vamos a indicar eso como "sort", usando "f" de "n.expandir". Estos son los sucesores. Ya que tenemos los sucesores en una lista ordenada, vamos a hacer lo siguiente: vamos a iterar sobre ellos, cada uno de los elementos de sucesores es "S". Para el sucesor "S" vamos, primero, a verificar si su costo "f" está dentro de la cota, y si está dentro de la cota, ahora vamos a verificar que no esté en la ruta. Si se cumplen estas dos condiciones, lo que vamos a hacer es agregarlo a la agenda. Ahora, si no se cumple esta condición, es decir, el estado "S" supera a la cota en costo, vamos a hacer un "else". Aquí es donde vamos a calcular la siguiente cota, entonces, vamos a comparar su costo "f" contra el "mínimo", y si es menor que el mínimo, vamos a actualizar el mínimo con el nuevo mínimo, que es "f" de "s". Ahora vamos a continuar donde termina este "if". Voy a poner aquí unas líneas para indicar que ese es el "else". Entonces, en caso de que "n" sí estuviera en la lista "X", tenemos que hacer un "pop" o extraer de agenda el elemento "n", y también lo vamos a quitar de la ruta. Vamos a ver qué pasa al terminar este "while". Entonces, al terminar el "while", vamos a establecer la nueva cota con "mínimo" y, sólo para que esté completo nuestro algoritmo en caso de que no exista una ruta, podría ser que ese mínimo sea infinito. En ese caso, pues, regresamos "ninguna ruta". Vamos a comentar algunos aspectos del algoritmo. Primero, respecto de este ordenamiento, el "sort" de los sucesores de "n". La complejidad de este "sort" es "n log n", pero no debe preocuparnos, puesto que el número de sucesores es el "brunching factor" y este "brunching factor" es generalmente pequeño. El segundo aspecto que hay que destacar del algoritmo es que consume muy poca memoria. Aquí, con cada elemento que se agrega a la ruta, vamos a agregar potencialmente a sus sucesores y estos tienen el tamaño..., o sea, el número de sucesores es igual a "b", el parámetro del "brunching factor" o "factor de ramificación". Entonces, esto va a crecer muy lentamente, porque no vamos a permitir llegar más allá a través de esta condición que está aquí, no vamos a agregar elementos que se vayan muy lejos en costo. Podríamos optimizar todavía más este código, verificando aquí también la condición de paro. Si nosotros tenemos, en esta línea, que agregamos la condición de paro, podríamos detectar en los sucesores cuándo ya se alcanzó la meta. Pero tendríamos que tener cuidado porque podría ser que se alcance y no sea la ruta óptima. Entonces, si aquí decidimos meter la condición de paro, habría que usar una estrategia similar a la que utilizamos con la ramificación y poda. Es decir, tendríamos que almacenar la ruta y, al final, determinar cuál fue la ruta óptima. Esto podría ahorrar algún tiempo de procesamiento porque ya no tendríamos que continuar en la siguiente iteración. Actualmente, garantizamos la optimalidad al sacar el nodo de la agenda -no lo sacamos, lo inspeccionamos- y cuando el objetivo es el que está en el tope, sabemos que ese es óptimo porque fuimos incrementando, cada vez, la cota con el mínimo. Entonces, está garantizado que vamos a encontrar la ruta óptima.
