El Algoritmo IDA*.
(C) Farid Fleifel Tapia, 1998
(Descarga el código de IDA* en C++)
Introducción
Los algoritmos de búsqueda heurística tradicionales como A* pueden llegar a necesitar un espacio de almacenamiento que crece de manera exponencial con la longitud de la solución del problema. Esto puede propiciar que, a pesar de que el problema tenga un coste temporal relativamente asequible, el coste espacial lo convierta en un problema intratable.
Es tal la importancia del coste espacial sobre el temporal en este tipo de problemas que sería adecuado llegar a un compromiso: Intentaremos ceder en nuestros requerimientos temporales a cambio de un uso más eficiente de la memoria que nos permita resolver problemas más grandes.
Los algoritmos que utilizaremos para lograr este objetivo se llaman genéricamente "algoritmos de búsqueda heurística con limitación de memoria". Los más utilizados son el IDA* (Iterative Deepening A*), y SMA* (Simplified memory A*).
El primero de estos algoritmos resulta sencillo de implementar y es una buena elección para muchos tipos de problemas, siendo el coste espacial lineal con la longitud de la ruta más larga que se explore. A cambio de esta drástica reducción en el espacio de almacenamiento necesario, convertimos la búsqueda de la solución en un proceso iterativo, que puede expandir varias veces los mismos nodos.
El algoritmo SMA* hace un uso más inteligente del espacio de almacenamiento y tiene la ventaja de usar toda la memoria de que disponga, de forma óptima. En este caso podemos considerar que el coste espacial es constante, aunque deberemos tener en cuenta que para poder obtener la solución óptima, la ruta entre el nodo inicial y el final deberá caber en la memoria disponible. El coste temporal de este algoritmo está muy relacionado con el tamaño de la memoria: Si en ella cabe todo el árbol de búsqueda, el algoritmo expandirá exactamente los mismos nodos que A*. Si no es así, las prestaciones se reducen. El uso de más memoria permite mejorar la eficiencia de la búsqueda.
En este trabajo se pretende desarrollar un programa que haga uso de un algoritmo de búsqueda heurística con limitación de memoria para resolver el problema del n-puzzle.
Se ha elegido el algoritmo IDA*, que se presenta a continuación, por su sencillez y por lo bien que se adapta a este problema en particular.
Como se verá más adelante, los resultados avalan el uso de este algoritmo frente a A* para tamaños grandes de problema, sobre todo en los casos en los que se realiza una poda de los nodos repetidos, lo cual ahorra una gran cantidad de tiempo.
El algoritmo de búsqueda IDA*.
Descripción del algoritmo.
El método IDA* (Iterative Deepening A*) consiste, como su nombre indica, en un algoritmo de profundización iterativa en el que se hace uso de la información heurística de que se dispone sobre el problema para decidir qué nodo expandir a continuación, y hasta dónde llegar en cada una de las iteraciones del proceso.
En este algoritmo, como en cualquier algoritmo de profundización iterativa, cada iteración es una búsqueda "primero en profundidad". En este caso la profundización se basa en la información heurística y terminará no a una determinada profundidad, sino cuando se llegue a un nodo cuyo coste de la función heurística de evaluación f = g + h sea mayor que el actual límite de coste de f. De esta forma en cada iteración se revisan todos los nodos con un coste de f menor o igual que el actual límite de coste. Además de esto se evalúan los nodos del contorno del árbol, que tienen un coste mayor que el actual límite de f, para calcular el límite de f que se utilizará en la siguiente iteración. Este nuevo límite será el valor mínimo de todos los valores de f de los nodos del citado contorno.
Todo esto se verá más claro después de analizar el seudocódigo del algoritmo y presentar un ejemplo ilustrativo.
Seudocódigo de IDA*
En adelante, "coste" representa un tipo de datos (tipicamente enteros o reales) en el que se almacenará el coste de los nodos. Para el problema del 8-puzzle basta con que "coste" sea de tipo entero.
función IDA*(problema) responde con una lista que contiene la ruta solución Entradas: problema: Estructura que contiene lo siguiente: estado Inicial : Estado a partir del que se comienza la búsqueda estado Final : Estado o estados objetivo de la búsqueda. entero NumOps : Número de operadores aplicables a los estados. vector de entero CosteOperador : Vector en el que se almacena el coste de los operadores. coste CosteMaximo : Cota superior del coste de la solución.
Variables: coste límite-f : En esta variable se almacena el límite del coste f para la iteración actual.
nodo raíz : Almacena el primer nodo del árbol. lista solución : Almacena la ruta solución.
//Se crea el nodo raíz. raíz = nuevoNodo(problema.inicial, problema.final)
//El primer límite-f es el coste-f del nodo raíz. límite-f = coste-f(raíz)
bucle hacer solución, límite-f = Contorno-DFS(raiz, límite-f) si no EsVacia(solución) responde con solución si límite-f ³ CosteMaximo responde con ERROR finbucle
función Contorno-DFS(nodoexp, límite-f) responde con lista solución, nuevo coste-f Entradas: nodo nodoexp : el nodo a expandir coste límite-f : límite actual de coste de f
Variables: coste siguiente-f : límite de coste-f correspondiente al siguiente contorno. Se inicializa con valor CosteMáximo.
// Si el coste de este nodo es mayor que el límite actual, devolvemos su coste. si coste-f(nodoexp) > límite-f responde con nulo, coste-f(nodoexp)
// Si es un nodo meta, respondemos con una lista inicializada con el nodo. si EsMeta(nodoexp) responde con lista(nodoexp), límite-f
// En otro caso expandimos el nodo. para cada operador op //Si existe un sucesor de nodoexp con el operador op si suc = sucesor(nodoexp, op) //hacemos una llamada recursiva a Contorno-DFS (solución, nueva-f ) = Contorno-DFS(suc, límite-f)
// Al retorno de Contorno-DFS, si tenemos solución, añadimos a la lista //el nodo actual. si no EsVacia(solución) InsertarLista(solución, nodoexp) responde con solución, límite-f finsi
// Si no hay solución comprobamos el valor de nueva-f, y si es menor // que siguiente-f lo almacenamos como valor provisional de limite-f para // la próxima iteración del algoritmo. siguiente-f = Minimo(siguiente-f, nueva-f) finsi //Si aún quedan operadores por comprobar continuamos iterando (bucle 'para') finpara
// Si llegamos hasta aquí es que desde el nodo nodoexp no se llega a una solución // de coste menor o igual que límite-f. Retornamos una lista vacía y el valor provisional // de límite-f para la próxima iteración.
responde con nulo, siguiente-f
Características de IDA*
IDA* es un método de búsqueda completo y óptimo, lo que quiere decir que siempre encuentra una solución si es que ésta existe y además garantiza encontrar la mejor solución de entre todas las posibles.
Este método tiene las mismas ventajas y desventajas que A*, excepto en lo referente al coste espacial. En este aspecto IDA* presenta notables ventajas ya que únicamente necesita un espacio proporcional a la longitud de la ruta más larga que se explore.
Esta limitación en el uso de la memoria resulta beneficiosa pero también tiene sus desventajas, ya que al convertir la búsqueda de la solución en un proceso iterativo expandiremos varias veces los mismos nodos. Esto es algo muy a tener en cuenta, ya que dependiendo de las características de los problemas a resolver obtendremos mejores o peores prestaciones.
En el mejor caso el coste temporal de IDA* puede ser muy similar al de A*, e incluso menor, ya que al ser un algoritmo simple y no necesitar de inserciones, borrados y reordenamientos en listas de prioridades tiene una menor sobrecarga por nodo. Este mejor caso ocurrirá cuando tengamos un problema en el que las heurísticas adopten valores aproximados al coste real desde el comienzo de la ejecución, ya que entonces se realizarán pocas iteraciones, expandiendo además pocos nodos en las iteraciones iniciales. Podemos asociar este caso con el problema del 8-puzzle cuando se usa la heurística de distancias
En el peor caso el coste temporal de IDA* se acerca al de un algoritmo de profundización iterativa habitual como el IDS (Iterative Deepening Search), es decir, en cada iteración se profundiza únicamente un nivel más en el árbol. Esto ocurre en problemas en los que los valores heurísticos son poco acertados, lo que provoca que en cada iteración aumentemos el contorno en sólo uno o dos niveles.
Esto sucede por ejemplo con el problema del viajante de comercio, o con el del 8-puzzle utilizando la heurística de aciertos.
A continuación se presenta una implementación en C++ seguida de unas pruebas del comportamiento del algoritmo, aplicado a la resolución del problema del 8-puzzle.
A partir de estas pruebas podremos comprobar las propiedades del algoritmo expuestas en este apartado.
Implementación.
El algoritmo ha sido implementado en C++ haciendo un uso extensivo de plantillas (templates) para facilitar la reutilización. El núcleo del mismo se implementa en el fichero IDA.h. El resto de los ficheros fuente contienen rutinas auxiliares así como la implementación de la clase CPuzzle, en la que se define el puzzle junto con los estados y operadores necesarios para poder ser aplicado en el algoritmo IDA*.
(Descarga el código de IDA* en C++)
La primera definición importante se halla en el fichero Heuristic.h Se trata de la clase problema.
template <class X> class CProblema
En esta clase almacenaremos la instancia del problema a resolver. Esta instancia se pasará más tarde a la clase IDA, que será la que resuelva el problema.
En este fichero también se implementa la clase CNodoHeur, que se encarga de almacenar los valores heurísticos y el estado en una única entidad.
template <class X> class CNodoHeur
Las operaciones de esta clase nos sirven para crear un nuevo nodo, así como para recuperar los valores almacenados en el mismo.
Las operaciones más importantes que realiza esta clase son la de creación de un nuevo nodo y la de generación de un sucesor:
template <class X> CNodoHeur<X>::CNodoHeur(X &est, X &final, int oper, coste G) template <class X> booleano CNodoHeur<X>::GenerarSucesor(CNodoHeur<X> &suc, int oper, coste costeOper, X &final)
Ya en el fichero IDA.h nos encontramos con el núcleo del algoritmo IDA*, incluído en la clase IDA:
template <class X> class IDA
En esta clase se utiliza una lista en la que se almacenará el árbol de búsqueda. Es suficiente con una lista ya que sólo exploramos una rama del árbol cada vez.
Se incluyen gran cantidad de métodos para el control de los nodos expandidos y del nivel alcanzado en el árbol. También pueden obtenerse la penetración y el factor de ramificación, calculado utilizando el método de Newton (implementado en el módulo raices.c++)
El constructor IDA(CProblema<X> *problema) almacena en el objeto IDA la instancia del problema y realiza las operaciones previas a la búsqueda.
La llamada a
booleano BuscarSolucion(CLista<X> &lista,TipoDePoda p)
pone en marcha el proceso de búsqueda. Este método se corresponde con la función que hemos llamado IDA*(problema) en el seudicódigo. Además, este método realiza las tareas de extracción y comprobación de la solución.
Otro método importante es
booleano ContornoDFS(coste limiteF, booleano &ok)
Las sucesivas llamadas recursivas a este método van examinando el árbol de estados hasta el límite de coste de la función f para la iteración actual. Además, se calcula el nuevo límite f, correspondiente a la siguente iteración. Podría decirse que este método constituye el núcleo del algoritmo IDA*:
template <class X> coste IDA<X>::ContornoDFS(coste limiteF, booleano &ok)
Este método se corresponde casi perfectamente con la función Contorno-DFS(nodoexp, límite-f) definida en el seudocódigo, y las explicaciones dadas allí son perfectamente válidas para esta rutina.
Existen algunos detalles de implementación, como la comprobación de la profundidad del árbol que no son imprescindibles para el funcionamiento, pero que nos proporcionan información muy valiosa a la hora de evaluar las prestaciones del algoritmo.
La única función realmente importante que queda por comentar es:
booleano Sucesor(CNodoHeur<X> &suc, int oper).
Con esta función se devuelve en la variable suc el sucesor del nodo actual, resultante de aplicar el operador oper. Si ese sucesor existe, se devuelve TRUE. en otro caso se devuelve FALSE.
Esta función es importante también porque dentro de ella se realiza la poda
Este método se limita a llamar al método GenerarSucesor de la clase CNodoHeur y a comprobar después si se ha obtenido el sucesor.
En caso de que se haya podido obtener, aún hay que comprobar que no se haya generado antes (utilizando las funciones de poda). Si se encuentra entre los nodos expandidos, no se volverá a expandir.
Las funciones de poda son
booleano PodaParcial(CNodoHeur<X> &suc) booleano PodaTotal(CNodoHeur<X> &suc)
La función de poda parcial comprueba únicamente si el nodo "abuelo" del nodo actual es idéntico a él. Esto sirve para evitar que en problemas en los que los operadores generen un sistema de producción conmutativo, vayamos deshaciendo los pasos que hemos tomado. En el caso del 8-puzzle esto evitaría expansiones en ciclo del tipo "izquierda", "derecha", "izquierda", "derecha", lo cual puede ahorrar una gran cantidad de tiempo, como veremos más adelante en las pruebas.
La función de poda total recorre toda la rama del árbol almacenada para comprobar si el estado actual se ha generado anteriormente. Puede que haya problemas en los que esto suponga una mejora importante con respecto a la función de poda parcial, pero como veremos, en el caso del 8-puzzle esto no es así.
Las demás funciones tienen menos relevancia y no las comentaremos. Puede consultarse el código fuente para más información.
Con esta implementación podemos aplicar el algoritmo de búsqueda IDA* a cualquier problema siempre y cuando definamos una clase problema con su función GeneraSucesor, su función de cálculo del valor de la heurística y un operador de igualdad que nos permita saber cuándo tenemos un nodo meta.
Esto se ha hecho con el problema del 8-puzzle implementando la clase CPuzzle, contenida en los ficheros CPuzzle.c++ y CPuzzle.h
A continuación comentaremos los resultados obtenidos tras la aplicación del algoritmo a diferentes problemas.
Resultados.
Se han efectuado diversas pruebas para problemas de complejidad variable, teniendo en cuenta diferentes opciones de poda y diferentes heurísticas.
A continuación incluímos una muestra de los resultados obtenidos en forma de varias ejecuciones del programa de búsqueda para dos problemas concretos:
Prueba 1
Heuristica aciertos. Sin poda. Tiempo de usuario:1.540 seg Longitud de la solucion: 14 Numero de nodos expandidos: 90510 Numero de nodos repetidos (no reexpandidos): 0 Penetracion (L/T): 0.000155 Factor de ramificacion: 2.161650 (OK) Maximo nivel del arbol (maximo numero de nodos en memoria simultaneamente): 15
Heuristica aciertos. Poda parcial. Tiempo de usuario:0.040 seg Longitud de la solucion: 14 Numero de nodos expandidos: 1648 Numero de nodos repetidos (no reexpandidos): 588 Penetracion (L/T): 0.008495 Factor de ramificacion: 1.580369 (OK) Maximo nivel del arbol (maximo numero de nodos en memoria simultaneamente): 15
Heuristica Distancias. Sin poda Tiempo de usuario:0.500 seg Longitud de la solucion: 14 Numero de nodos expandidos: 15355 Numero de nodos repetidos (no reexpandidos): 0 Penetracion (L/T): 0.000912 Factor de ramificacion: 1.886209 (OK) Maximo nivel del arbol (maximo numero de nodos en memoria simultaneamente): 15 Heuristica Distancias. Poda parcial. Tiempo de usuario:0.040 seg Longitud de la solucion: 14 Numero de nodos expandidos: 416 Numero de nodos repetidos (no reexpandidos): 147 Penetracion (L/T): 0.033654 Factor de ramificacion: 1.409206 (OK) Maximo nivel del arbol (maximo numero de nodos en memoria simultaneamente): 15
Prueba 2
Heuristica aciertos. Sin poda. Tiempo de usuario:6.780 seg Longitud de la solucion: 16 Numero de nodos expandidos: 397928 Numero de nodos repetidos (no reexpandidos): 0 Penetracion (L/T): 0.000040 Factor de ramificacion: 2.152963 (OK) Maximo nivel del arbol (maximo numero de nodos en memoria simultaneamente): 17 Heuristica aciertos. Poda parcial. Tiempo de usuario:0.140 seg Longitud de la solucion: 16 Numero de nodos expandidos: 5356 Numero de nodos repetidos (no reexpandidos): 1943 Penetracion (L/T): 0.002987 Factor de ramificacion: 1.609573 (OK) Maximo nivel del arbol (maximo numero de nodos en memoria simultaneamente): 17
Heuristica aciertos. Poda total. Tiempo de usuario:0.180 seg Longitud de la solucion: 16 Numero de nodos expandidos: 5354 Numero de nodos repetidos (no reexpandidos): 1943 Penetracion (L/T): 0.002988 Factor de ramificacion: 1.609531 (OK) Comprobacion: 0.000000 Maximo nivel del arbol (maximo numero de nodos en memoria simultaneamente): 17 Heuristica distancias. Sin poda. Tiempo de usuario:3.970 seg Longitud de la solucion: 16 Numero de nodos expandidos: 126838 Numero de nodos repetidos (no reexpandidos): 0 Penetracion (L/T): 0.000126 Factor de ramificacion: 1.995628 (OK) Maximo nivel del arbol (maximo numero de nodos en memoria simultaneamente): 17 Heuristica distancias. Poda parcial. Tiempo de usuario:0.060 seg Longitud de la solucion: 16 Numero de nodos expandidos: 1390 Numero de nodos repetidos (no reexpandidos): 503 Penetracion (L/T): 0.011511 Factor de ramificacion: 1.463104 (OK) Maximo nivel del arbol (maximo numero de nodos en memoria simultaneamente): 17 Heuristica distancias. Poda total. Tiempo de usuario:0.070 seg Longitud de la solucion: 16 Numero de nodos expandidos: 1388 Numero de nodos repetidos (no reexpandidos): 503 Penetracion (L/T): 0.011527 Factor de ramificacion: 1.462952 (OK) Maximo nivel del arbol (maximo numero de nodos en memoria simultaneamente): 17
Discusión.
Realizando varias pruebas como las del apartado anterior recopilamos los suficientes datos como para presentar los siguientes resultados:
Para la heurística de aciertos podemos apreciar que el coste temporal aumenta rápidamente con el tamaño del problema.
Las rutinas de poda ayudan a que el tiempo necesario se reduzca, pero aún así la explosión exponencial se produce bastante pronto.
El único caso en el que los resultados son aceptable es en el de la poda parcial.
Podríamos pensar que la poda total, al eliminar más nodos a expandir del árbol, conseguiría unos tiempos menores que la poda parcial.
Sin embargo la sobrecarga por nodo que supone el tener que explorar la rama entera buscando nodos repetidos hace que la ventaja de la menor expansión de nodos no sea suficiente, al menos en el problema del 8-puzzle. Para otros tipos de problema podría llegar a ser más efectivo el realizar una poda total, pero no es ese el caso del problema que nos ocupa.
Utilizando la heurística de distancias tenemos unos resultados mucho más aceptables.
El coste para problemas de tamaño hasta 30 permanece suficientemente acotado, sobre todo si se utiliza alguna de las estrategias de poda.
En este caso la poda parcial sigue siendo una mejor opción que la total. En el intervalo de tamaños de problema que hemos considerado esto no parece obvio, pero sería de esperar que para tamaños mayores de problema esto se apreciase con más claridad.
La comparación entre las dos heurísticas no admite dudas. La heurística de distancias es claramente mejor que la de aciertos. Con la de aciertos ni siquiera podemos encontrar la solución a un problema de tamaño 28 en un tiempo razonable utilizando el algoritmo original, sin poda. Sin embargo con la heurística de distancias, usando el algoritmo sin poda el tiempo para resolver el mismo problema es de 3.5 segundos.
La comparación utilizando algún tipo de poda resulta igual de clara a favor de la heurística de distancias, aunque en este caso las diferencias temporales sean menores.
Esto confirma que el uso de una heurística mejor informada que otra puede ser de gran importancia para la resolución de este tipo de problemas. Una buena función heurística puede transformar la resolución de un problema concreto de intratable a asequible.
En cuanto al uso de memoria, en todos los casos estudiados la memoria utilizada se reduce a la necesaria para almacenar los nodos del camino solución. En ningún caso de los probados se explora un camino más largo que el camino solución. Por tanto, podemos afirmar que salvo raras excepciones, el coste espacial de un problema con una solución de talla n será de n + 1 nodos. (si la solución tiene n pasos, necesitaremos almacenar n + 1 nodos, contando el nodo inicial)
Cada nodo necesitará una cantidad constante de memoria, que dependerá del problema que estemos resolviendo. En todo caso, el coste espacial será de k · (n + 1) bytes, siendo k una constante que representa el número de bytes por nodo. Por tanto el coste espacial de IDA es O(n).
Un hecho a destacar es que existe una gran variabilidad en los tiempos de ejecución de las diferentes pruebas, incluso para una misma longitud del camino solución. Esto es debido a que la eficiencia del valor devuelto por la heurística es crucial a la hora de ahorrar iteraciones de cálculo.
En los casos en los que las piezas están muy lejos de su posición destino, las heurísticas devuelven valores más altos y el proceso de profundización requiere menos iteraciones.
Cuando no ocurre esto y las piezas están cerca de su posición objetivo pero desordenadas de tal forma que la ruta solución tiene un gran número de pasos, como los valores de las heurísticas son reducidos desde el principio, es necesario realizar varias más iteraciones hasta conseguir llegar a la solución.
Esto explica también el hecho de que el factor de ramificación y la penetración presenten valores que pueden variar ampliamente para problemas resueltos utilizando una misma heurística y un mismo algoritmo de poda.
Como ejemplo podemos destacar que para la heurística de distancias, sin efectuar poda, en las pruebas que hemos efectuado el factor de ramificación varía desde un mínimo de 1.048883, valor que se obtiene al resolver una instancia de problema de talla 14, hasta un 1.995628, que se obtiene al resolver una instancia de talla 16.
Entre los dos extremos obtenemos un gran abanico de valores. A la hora de calcular la media esta queda en un valor de aproximadamente 1.4
Si realizamos poda este valor disminuye, especialmente con la poda parcial. En este caso el máximo valor del factor de ramificación obtenido de ente todas las pruebas realizadas ha sido de 1.589412
Si comparamos el algoritmo IDA* con A* vemos que los costes temporales son comparables. En el caso de la poda parcial IDA* puede ser hasta más rápido si está bien implementado.
En cuanto a número de nodos expandidos, IDA* es indiscutiblemente mejor, ya que por ejemplo para tamaños de problema de 24, A* necesitaría almacenar en memoria una media 39135 nodos usando la heurística de aciertos, y unos 1641 con la heurística de distancias [Russell 96]. IDA* sin embargo sólo necesitaría espacio para 25 nodos.
En cuanto al factor de ramificación, A* presenta valores notablemente menores, aunque esto es normal ya que al ser IDA* un proceso iterativo la reexpansión de nodos en cada iteración es inevitable.
Para A* con la heurística de distancias este parámetro se halla entorno a 1.25, mientras que, para IDA* sin poda, este parámetro, aunque muy oscilante, presenta un valor medio de alrededor de 1.4
En consecuencia, cuando nos enfrentemos a problemas en los que las necesidades espaciales sean importantes, podremos acudir a IDA* sin excesivas preocupaciones. En los casos en los que dispongamos de memoria suficiente, A* será casi siempre una mejor elección, pero la simplicidad de IDA* y sus buenas propiedades lo hacen una buena elección para una gran variedad de problemas en entornos con memoria limitada o en los que la velocidad no sea lo más importante.
Bibliografía.
Para realizar este trabajo se han tenido en cuenta principalmente las siguientes referencias:
[Nilsson, 87].- "Principios de Inteligencia Artificial". Nils J. Nilsson. Editorial Diaz de Santos (1987).
[Rich, 94].- "Inteligencia Artificial". Segunda edición. Elaine Rich. Kevin Knight. Editorial McGraw-Hill. (1994).
[Russell, 96].- "Inteligencia Artificial, un enfoque moderno". Stuart Russell. Peter Norvig. Editorial Prentice Hall. (1996).