Hoy vamos a tratar de modificaciones del algoritmo A estrella, buscando que tenga un mejor desempeño o que tengamos un mejor control sobre los recursos computacionales que consume. Vamos a comenzar por identificar cuáles son los puntos débiles o puntos de mejora del algoritmo Cuando analizamos la complejidad computacional del algoritmo, identificamos que la heurística es fundamental para definir qué tan eficiente es el algoritmo. Una heurística buena nos puede llevar rápidamente a encontrar la meta, pero una heurística débil resulta en un consumo exponencial, tanto de memoria, como de tiempo. Una primera modificación al algoritmo A estrella consiste en limitar los recursos computacionales que consume. Cuando vimos los algoritmos de búsqueda ciega, utilizamos una cota de profundidad para limitar los recursos computacionales, tal es el caso del algoritmo de profundidad limitada o DLS. En el algoritmo DLS existía un parámetro "c", que era la cota de profundidad, y cualquier estado que estaba más allá de esa cota, era ignorada por el algoritmo. Típicamente, para los algoritmos de búsqueda informada, no se establece una cota de profundidad, sino una cota de costo. Vamos a modificar el algoritmo A estrella para que cualquier vértice que se quiera expandir o agregar a la agenda se compare contra esta cota. Si el costo "f", es decir, la suma del costo acumulado con la estimación de la heurística al nodo meta, es mayor que la cota, entonces ignoramos ese estado. Para ilustrar el efecto de la cota sobre el algoritmo A estrella, vamos a retomar el ejemplo que vimos para ilustrarlo originalmente. Se muestra la evolución del estado de la agenda y el conjunto de expandidos tras cuatro expansiones. Consideremos qué habría sucedido en la versión acotada de A estrella si ponemos la cota "c" igual a seis. Esto es una unidad mayor que la profundidad de la solución "d" que, en este caso, es de cinco. Con esta cota, los estados coloreados en rojo no se habrían agregado a la agenda, pues superan la cota. Al acotar el costo de los estados a considerar, observamos que la agenda crece muy poco. De hecho, el algoritmo mantiene, desde la primera expansión hasta la cuarta, únicamente dos estados en la agenda. Este ahorro de memoria pudo haber sido mayor con una cota más justa. Considerando ahora una cota de cinco, que es igual a la profundidad de la meta, puede apreciarse que el algoritmo utiliza el mínimo de memoria para la agenda. Los estados tachados no se habrían agregado en primer lugar. En este ejemplo, la agenda no crece de tamaño. Concluimos que el máximo ahorro de memoria que garantiza encontrar la solución, se da cuando la cota corresponde con la profundidad de la meta. Observemos que la modificación propuesta al algoritmo nos da control sobre qué tan lejos puede llegar la exploración y esto está relacionado con los recursos computacionales. Sin embargo, lo que observamos aquí es que el crecimiento de memoria sigue siendo exponencial con el mínimo de la profundidad de la solución y la cota. Como no sabemos a qué profundidades se encuentra la solución, tres cosas pueden suceder. En el primer caso, si "c" es menor que "d", no vamos a encontrar la solución. La cota torna el algoritmo en un algoritmo incompleto. El segundo caso es cuando la cota es igual a la profundidad de la meta. En este caso tenemos el mejor de los escenarios, el algoritmo va a encontrar la solución óptima y también va a ahorrar el máximo de recursos computacionales. En el tercer caso tenemos que la cota supera la profundidad de la meta. Aquí vamos a tener un ahorro de memoria marginal o nulo, si la magnitud de la diferencia de estos dos parámetros es grande. Hasta el momento hemos considerado que la heurística es admisible y monotónica, pero ¿qué sucede si no lo es o no sabemos si lo es? Vamos a ver modificaciones al algoritmo A estrella que nos permiten tratar con este tipo de heurísticas. Primero hay que entender cuál es el efecto de que la heurística sea no monotónica. Si aplicamos al algoritmo A estrella una heurística no admisible, vamos a encontrar, posiblemente, una solución sub-óptima. Esto, en principio, no es tan grave. Pero, si queremos garantizar encontrar la solución óptima, entonces debemos hacer algunas modificaciones. La primera modificación que vamos a proponer consiste en el tratamiento que le damos al conjunto de expandidos. En este caso no vamos a utilizar un conjunto, sino una tabla de dispersión. ¿Cómo vamos a utilizar esta tabla de dispersión o diccionario? Cuando teníamos el conjunto de expandidos, lo que hacíamos antes de expandir un nodo o agregarlo a la agenda, era verificar si este nodo ya se había expandido. Si existía en el conjunto, no se expandía. Ahora vamos a utilizar el diccionario de la siguiente manera. También vamos a verificar si existe o no en el diccionario. Si no existe, vamos a expandirlo. Pero si existe, tiene la posibilidad de ser expandido siempre que la profundidad a la que lo encontremos sea menor a la profundidad almacenada en el diccionario. Si encontramos un nodo que ya se ha expandido y la segunda vez que lo encontramos tiene una profundidad menor, vamos a actualizar la entrada que tenemos en el diccionario con el nuevo nodo y la profundidad de la nueva ruta. Para el algoritmo A estrella vamos a hacer lo siguiente. Una vez que encuentre una solución, esta también posiblemente va a ser sub-óptima. La vamos a almacenar y vamos a establecer una cota, pero ahora no de profundidad, sino de costo. Esta cota de costo se va a comparar contra la profundidad acumulada de los nodos que pretendan entrar a la agenda o que se saquen para expansión. Si alguno de estos estados tiene una profundidad que supere la cota, será ignorada. Vamos a presentar un ejemplo del algoritmo BBA estrella. Es el ejemplo del metro de la Ciudad de México. Del lado derecho tenemos una tabla con una función heurística. La heurística es una estimación de la distancia al estado objetivo, en este caso, el estado "P". La heurística es una aproximación muy ruidosa de la distancia real, a veces se queda debajo del valor real, a veces sobreestima. Por ejemplo, la heurística estima un costo de 900 para el estación "E", sin embargo, el costo real es de 745. Además, el ruido en la heurística la hace no monotónica. Veamos, por ejemplo, cómo la estimación del costo a la meta, para el estado "A", no es menor que la estimación para "Z", sumado con el costo de la transición. No se cumple la desigualdad del triángulo. A BBA estrella no le importa esto, puede explotar la heurística ruidosa. Comenzamos como en un algoritmo A estrella convencional, agregando la meta a la agenda. La agenda es una cola de prioridad con el costo "f" como criterio de ordenamiento. La lista de expandidos ahora es una tabla de dispersión o diccionario, donde, en las parejas a almacenar, la llave es el estado expandido y el valor el costo real acumulado "g" del estado llave. Para determinar si debemos agregar o expandir nodos a la agenda, pedimos que el nodo no se encuentre en la tabla de expandidos, o bien que el costo "g" de "n" de la ruta al estado "N" actual, sea menor o igual que el almacenado como valor en la tabla. Continuamos. Expandimos a "B". Agregamos los estados "G", "A", "S", y "H" a la agenda. En la tabla de expandidos agregamos a "B" con costo cero. El estado con menor costo "f" es "S". Es el estado al frente de la cola de prioridad. "S" genera al estado "O". "S" se registra en la tabla de expandidos con un costo de 456. El estado de menor costo "f" ahora es "O". Al expandir el estado "O", agregamos a los estados "D" e "I". Registramos a "O" en expandidos con costo 748. El siguiente en salir será "A". "A" genera a "Z". "Z" queda al frente de la cola de prioridad. Al sacar a "Z" descubrimos la meta. Recuperamos la ruta. En este caso, "B", "A", "Z", "P". Esta ruta podría ser sub-óptima porque la heurística no es admisible. Vamos a guardar la ruta como "ruta subíndice 1". El costo de esta solución es de 1734. En lugar de terminar y regresar la ruta, vamos a continuar la búsqueda, pero pondremos una cota para las funciones "g" de "n". Para decidir si un estado entra a la agenda o si un estado de la agenda que se saca se expande, pediremos que el costo acumulado "g" del estado sea menor o igual al costo de la cota. Si el costo "g" del estado es mayor, no vamos a permitir el ingreso del estado a la agenda ni tampoco su expansión. Continuamos. Estamos pendientes de la cota "C". El estado al frente de la cola de prioridad es "I". Al expandirlo, encontramos otra ruta a "P". En este caso, "B", "S", "O", "I", "P". El costo de la nueva ruta es de 1575. Es una mejor ruta. Valió la pena el continuar buscando. A la ruta la denotamos como "ruta subíndice 2". Es una ruta más larga en pasos, pero más corta en costo. Nuevamente, actualizamos la cota, de 1734, ahora, a 1575. La condición que estamos verificando para agregar o expandir nodos, es que éstos tengan un costo acumulado menor o igual a la cota. Vemos que el estado al frente de la cola es el estado "D" con un costo acumulado de 1206. Como es menor que la cota, 1575, lo vamos a expandir. Los sucesores "J" y "C" sólo se agregan a la agenda si su costo acumulado es menor a la cota. Vemos que ambos superan la cota, por lo tanto, los vamos a ignorar. El siguiente al frente es el estado "G". Agregamos a sus sucesores "R" y "L" a la agenda, pues están dentro de la cota. Ahora es el turno de "H", agregamos a sus sucesores "J", "V", y "R". "J" será el siguiente en salir. Evaluamos cuándo debemos agregar a "D" a la agenda, pues ya se había expandido antes y está en la tabla con un costo de 1206. Su costo acumulado es de 1357, significa que esta ruta es peor que la anterior y sería infructuoso expandirlo nuevamente. Si el costo acumulado para "D" fuera menor que el costo de la tabla, tendríamos que haber actualizado la tabla con el costo de la nueva ruta. Continuamos. El siguiente nodo a sacar es "L". "T", su sucesor, también supera la cota de costo, lo ignoramos. Es el turno de "V". No agrega nada. El siguiente al frente es "R". Su sucesor, el estado "U", tiene un costo acumulado que supera la cota, lo ignoramos también. Queda otra instancia del nodo "R" en la agenda, la sacamos. Su costo acumulado es de 1391, está dentro de la cota. Sin embargo, ya se había expandido una "R" a un costo de 1149. Como esta segunda ruta a "R" tiene un costo superior, no vamos a expandir el nodo. La agenda se ha vaciado. Regresamos la mejor ruta encontrada, en este caso, la ruta "subíndice 2".
