Hoy presentaremos el algoritmo de búsqueda con profundidad limitada. El algoritmo de búsqueda con profundidad limitada es una variación del algoritmo de búsqueda primero en profundidad. Anteriormente, mencionamos que vamos a usar el algoritmo DFS y BFS como base para construir algoritmos más sofisticados. El algoritmo que veremos hoy se denomina también como DLS por sus siglas en inglés, que significan "depth limited search". Este algoritmo, básicamente, es un algoritmo DFS pero con dos modificaciones. La primera modificación es que vamos a tener un parámetro adicional, que es la cota de profundidad. El significado de este parámetro es que el algoritmo no puede superar esta cota, es decir, cualquier estado que esté más allá de esta profundidad va a ser ignorado por el algoritmo. La segunda modificación es que el algoritmo no utiliza una lista o un conjunto de expandidos. Como ya vimos, el algoritmo DFS es muy atractivo respecto de la memoria cuando se trata de la agenda, pero no es tan atractivo cuando se trata de ese conjunto de expandidos. Cuando hicimos el análisis asintótico del consumo de memoria del algoritmo DFS, identificamos que la agenda crece de manera lineal con la profundidad. Sin embargo, el conjunto de expandidos crece a la par con el tiempo que le toma al algoritmo encontrar la solución, esto es exponencial con la longitud de la trayectoria más larga en el grafo. Esto no es bueno. Sin embargo, en este algoritmo lo que vamos a hacer es borrar por completo ese conjunto de expandidos. Con las modificaciones que proponemos, entonces, el algoritmo sà va a trabajar doble, va a poder expandir un nodo más de una vez, pero la ventaja que vamos a tener es que va a consumir mucha menos memoria que el algoritmo DFS. Vamos a ilustrar la operación del algoritmo DLS en el ejemplo de encontrar la ruta de la estación Bellas Artes a la estación Pino Suárez. El algoritmo agrega el estado inicial a la agenda. Empezamos la iteración. Sacamos al estado "B" de la agenda, expandimos a "B". "B" tiene cuatro sucesores: "G", "A", "S" y "H". Agregamos los cuatro a la agenda. Indicamos en el subÃndice el estado del que vienen y, como superÃndice, la profundidad del vértice. Por ser la primera expansión, todos tienen profundidad uno. Sacamos el estado "H" y lo expandimos. Sus sucesores, "R", "J" y "V", tienen profundidad dos. Sacamos el tope de la pila, el estado "V". Como DLS es una búsqueda en profundidad, observamos que la profundidad de los nodos está aumentando. Aún estamos dentro de la cota. No hay sucesores de "V" que tengamos que agregar. En el siguiente paso se saca a "J" de la agenda. Con su expansión, se agrega el estado "D". "D" ha alcanzado la cota de profundidad. Sacamos a "D" de la agenda. DLS no puede agregar nodos que superen la cota de profundidad. Los sucesores de "D" son ignorados. El nodo, simplemente, no se expande. El tope de la pila ahora es "R", lo sacamos. Al expandirlo, agregamos "G" y a "U". Sacamos de la agenda a "U". No se expande porque su profundidad es tres. Sus sucesores superarÃan la cota. Ahora sacamos a "G", tampoco se expande. El siguiente estado en salir es "S". Al expandir a "S", se agrega "O" a la agenda. Se saca "O", agregamos dos sucesores, el estado "I" y el estado "D". En el tope queda "D", lo sacamos. No se expandirá dado que su profundidad es igual a la cota. Similarmente, para "I" no agregamos sucesores. El tope de la pila ahora es "A", lo sacamos. Al expandir "A", agregamos a "Z". "Z" es el tope, lo sacamos. Al expandirlo, descubrimos a "P", nuestra meta. Antes de terminar, recuperamos la ruta: "P" viene de "Z", "Z" viene de "A", "A" viene de "B". La ruta es "B", "A", "Z", "P". Ahora vamos a analizar el desempeño del algoritmo DLS. El primer aspecto que vamos a considerar es el de consumo de memoria. Recordemos que tenemos el factor de ramificación representado con la letra "b" y, en este caso, para este algoritmo tenemos el parámetro "c", que representa la profundidad de corte. La única estructura que consume memoria es la agenda y ésta crece de manera lineal. Entonces, nuestro algoritmo es "O", "b" por "c". El segundo aspecto que vamos a considerar es el del tiempo que tarda en resolver el problema. En este caso, el algoritmo va a consumir un tiempo igual a "b" elevado a la "c". Entonces, es un consumo exponencial en tiempo. Sin embargo, lo que hay que notar aquà es que nosotros decidimos cuál es el parámetro "c", y podemos acotar o seleccionar este parámetro de acuerdo a las caracterÃsticas del problema. Tenemos control completo sobre cuánto se va a tardar el algoritmo en ejecutar la búsqueda. Esto es muy bueno porque limitamos los recursos computacionales consumidos por el algoritmo. Respecto de la calidad de la solución, vamos a recordar que el algoritmo DFS, sobre el que está basado DLS, no es óptimo en el número de pasos. En este caso, el algoritmo DLS va a heredar esta caracterÃstica. Si la cota que nosotros establecimos es superior a la distancia a la que se encuentra el objetivo, es decir, el parámetro "d", el algoritmo no nos va a garantizar la solución óptima. El algoritmo sólo garantiza la solución óptima cuando nosotros establecemos la cota igual a la profundidad de la meta. Pero, como no sabemos cuál es la profundidad de la meta, no podemos a priori establecerla de tal manera que nos dé la solución óptima. En consecuencia, el algoritmo es subóptimo. Respecto de la completez del algoritmo, es decir, si siempre nos da una respuesta, lo que podemos decir es que, como nosotros no sabemos a qué profundidad se encuentra la meta, si nosotros establecemos una cota inferior a esa profundidad, el algoritmo no la va a encontrar. Entonces, es un algoritmo incompleto. Vamos a presentar el algoritmo de profundidad iterada. El algoritmo de profundidad iterada es una modificación del algoritmo de profundidad limitada. El problema que tenemos con el algoritmo de profundidad limitada es que no nos regresa la solución óptima, si nosotros establecemos una cota más allá de la profundidad del objetivo o la meta. Como nosotros no sabemos a qué profundidad se encuentra el objetivo, no podemos de antemano establecer la profundidad necesaria para que nos regrese la solución óptima. Con la modificación que vamos a proponer, vamos a encontrar la solución óptima. El algoritmo de profundidad iterada. En inglés se le conoce como "iterative deepening", lo vamos a abreviar ID. El algoritmo ID tiene dos entradas: la primera es el estado inicial y la segunda es la función de paro. El algoritmo realmente es muy simple. Vamos a requerir de un contador, llamémosle "i", el cual vamos a inicializar con un valor de uno. La solución, vamos a considerar que no la tenemos y la vamos a inicializar como "no existente". Después, vamos a entrar en un ciclo mientras la solución no se encuentre. Y aquÃ, vamos a hacer uso del algoritmo DLS. Entonces, invocamos el algoritmo DLS. Le vamos a pasar los argumentos: nuestro estado inicial, nuestra función de paro y la cota. Pero aquÃ, como cota, vamos a pasar nuestro contador. Después vamos a incrementar el contador. Ya terminamos nuestro bloque asociado a esta repetición "while". Terminando, simplemente vamos a regresar la solución. Como puede apreciarse, básicamente el algoritmo de profundidad iterada lo que hace es una serie de invocaciones al algoritmo DLS, en la cual se va incrementando, en cada invocación, la profundidad de corte. De esta manera, mientras estemos abajo de la profundidad de la solución, DLS nos va a regresar una solución inexistente y el algoritmo va a continuar iterando. AquÃ, mientras la solución sea igual a "none", o sea que no exista, va a continuar iterando. En el momento en que le demos la profundidad de la solución, o sea, que esta profundidad "i" sea igual a nuestro parámetro "c", entonces, DLS la va a encontrar y nos la va a dar. En ese momento, la solución va a ser diferente de "none" y la regresamos. Ahora, vamos a presentar el algoritmo de búsqueda en profundidad con ramificación y poda. En inglés se le conoce como "depth first branch and bound". Vamos a usar sólo las siglas. Esta es una mejora sobre el algoritmo de profundidad iterada: el algoritmo DFBB tiene tres argumentos. El primero es el estado inicial, el segundo es la función de paro, y el tercero es la cota de profundidad a la cual la vamos a denominar "c". Esta cota va a servir para controlar hasta dónde se van a expandir los nodos. Ahora, vamos a inicializar primero nuestra solución como no existente. Después, vamos a verificar la condición trivial, esto es, si la función de paro se satisface para el estado inicial. Si esto es cierto, entonces, regresamos la ruta, que aquà va a ser trivial. Para ello, asumimos que existe una función que nos encuentra la ruta. Si la condición trivial no se cumple, lo siguiente es inicializar la agenda con el estado inicial. Entonces, vamos a agregar el estado inicial a la agenda. Ya que terminamos de inicializar, lo siguiente es entrar en un ciclo de iteración. El ciclo de iteración lo voy a escribir de este lado. Aquà ponemos que continúa en "alfa". En el ciclo "while" vamos a poner la condición de que la agenda no esté vacÃa. Aquà estoy indicando, de esta manera, que el número de elementos de agenda sea mayor que cero. Aquà voy a escribir un conjunto de instrucciones que se van a repetir mientras esto sea cierto. La primera es extraer de la agenda el tope de la pila, lo vamos a denominar "n". Lo siguiente es ver si podemos expandir a este nodo. Para ello, vamos a verificar su profundidad. Si su profundidad es menor que la cota de profundidad, entonces, vamos a proceder a expandir este nodo. Estamos extrayendo cada uno de los sucesores de "n" con la función "expandir". A cada uno de ellos le estamos denominando "s". Lo siguiente es verificar la condición de paro para cada uno de los sucesores de "n". Si la condición se verifica, a diferencia de DLS, aquà no nos vamos a detener. Estos pasos son los dos pasos más importantes y es la diferencia entre este algoritmo y el algoritmo DLS. El primer paso es almacenar o recordar la solución que hemos encontrado. Aquà vamos a encontrar la ruta a partir de "s". Nos va a interesar continuar buscando por soluciones, pero que tengan profundidades menores a la profundidad de esta solución, es decir, que sean mejores. Entonces, en este paso vamos a actualizar la cota. La nueva cota va a ser igual a la profundidad de "n". Entonces, nuestra nueva cota va a ser la profundidad del padre del nodo "s", que es la solución. Por lo tanto, si volvemos a encontrar otra solución, si se vuelve a cumplir esta condición, esa solución va a ser más corta, va a tener menos pasos. Esta es la primera condición. Si no se cumple, entonces, vamos a hacer un "else". Va a ser simplemente agregar a la agenda el nodo "s". Con ello, hemos terminado el ciclo iterativo. Al terminar el ciclo, vamos a hacer el "return" de la solución. Aquà tenemos una tabla comparativa de los recursos computacionales que utilizan los algoritmos. Lo que podemos ver es que, en términos de memoria, las mejoras que propusimos con los algoritmos DLS, ID y DFBB, todas tienen crecimiento lineal. Entonces, ganamos bastante. Este algoritmo, prácticamente no consume memoria. Respecto del tiempo que se va a tardar el algoritmo en resolver el problema, observamos que los algoritmos DLS y DFBB, ambos crecen a razón de "b" a la "c", mientras que el algoritmo ID crece a razón de "b" a la "d". Si vamos a encontrar la solución, en general "d" es menor que "c". Entonces, parecerÃa como más atractivo el algoritmo de profundidad iterada. Sin embargo, hay que considerar que, con cada iteración, el algoritmo vuelve a empezar desde cero. Entonces, repite una y otra vez las mismas operaciones, entonces, no necesariamente va a ser la mejor opción. AquÃ, hay que hacer un balance entre la cota que nosotros seleccionamos, y que sabemos porque nosotros la estamos seleccionando que es adecuada para encontrar una solución en un tiempo razonable, y el tiempo que se tarda en iterar un algoritmo ID. Respecto de la calidad, podemos decir que DLS es subóptima, no nos garantiza la solución óptima, y los algoritmos ID y DFBB sà nos encuentran, nos garantizan la solución óptima. Respecto de la completez de los algoritmos, lo que observamos es que DLS es un algoritmo incompleto, ID es un algoritmo completo y DFBB es un algoritmo incompleto. Entonces, parecerÃa que ID es la mejor opción aquÃ. Pero recordemos, ID no está acotado de manera superior, entonces, podrÃa ser que consuma muchos recursos y no sabemos cuándo se va a detener. Sin embargo, con DLS y con DFBB, nosotros tenemos control de cuándo se va a detener, entonces, eso puede ser una ventaja a pesar de que no sea completo.
