Hoy vamos a comparar el desempeño de los algoritmos primero en profundidad y primero en anchura. Para poder compararlos, vamos a utilizar la herramienta presentada al inicio del curso, el análisis asintótico. [MÚSICA] Para poder aplicar el análisis asintótico, requerimos de identificar algunos parámetros del problema. Nos interesa conocer cómo crecen los recursos computacionales, la memoria y el tiempo, conforme vamos creciendo el tamaño del problema. Para ilustrar los parámetros que nos permitirán hacer el análisis asintótico, vamos a utilizar el ejemplo del grafo de estados-acciones del metro de la Ciudad de México. El primero de los parámetros es la longitud de la trayectoria más larga entre dos vértices del grafo. A este parámetro lo vamos a denominar m. En el ejemplo que tenemos, ese parámetro m vale 17. El siguiente de los parámetros es conocido como factor de ramificación, arborescencia o, en inglés, branching factor. El factor de ramificación se define como el número de acciones posibles para cada uno de los estados de nuestro grafo. En este caso, tenemos un número variable de acciones. Algunos vértices tienen dos opciones, algunos tienen una, otros tienen cuatro. Entonces, algo que se utiliza es el valor promedio del número de acciones posibles. Aquà vamos a calcularlo. Tenemos tres vértices que tienen cuatro salidas, seis vértices con tres salidas, nueve vértices con dos y cuatro vértices con una. Entonces, el valor promedio nos da 2.36. Este serÃa el factor de ramificación en este caso. Para ilustrar los siguientes dos parámetros, vamos a recurrir a esta representación de un árbol de búsqueda. El primero de los parámetros es la profundidad del vértice y se define como la distancia en número de pasos a partir del estado inicial. A este parámetro lo vamos a denotar con la letra n. En este ejemplo, si ponemos n = 0, solo tenemos el estado inicial. Con n = 1, tenemos a los sucesores del estado inicial. Como el factor de ramificación es tres, tenemos tres sucesores. Con n = 2, vamos a tener a los sucesores de los sucesores del estado inicial. Como tenÃamos tres y tenemos tres sucesores para cada uno de ellos, en total tenemos nueve vértices que tienen una profundidad igual a dos. Si ponemos profundidad igual a tres, terminamos con nueve por tres, 27 sucesores o nodos que tienen esta profundidad. El último de los parámetros va a ser la profundidad de la solución. En el árbol de búsqueda, cada vértice tienen su propia profundidad. En particular, la profundidad de la solución va a ser importante para analizar los algoritmos. A la profundidad de la solución la vamos a denotar con la letra d. En este ejemplo, tenemos ilustrada la profundidad de la solución igual a cuatro. Ahora vamos a ilustrar de manera informal cómo se comporta el algoritmo primero en profundidad. La agenda primero se inicializa con el estado inicial. Después vamos a sacar el estado inicial y vamos a agregar a sus sucesores. Tenemos tres estados en la agenda. También a estos estados se les denomina la frontera de búsqueda. Tenemos un estado en el conjunto de expandidos. En el siguiente paso, sacamos el elemento en el tope de la pila, lo agregamos a la lista de expandidos, agregamos sus sucesores a la agenda. En estos momentos, hay cinco estados en la frontera, dos a profundidad uno y tres a profundidad dos. En el siguiente paso, expandimos el último elemento en entrar a la agenda. Ahora tenemos tres estados en el conjunto de expandidos y siete estados en la frontera, dos de profundidad uno, dos de profundidad dos y tres de profundidad tres. Para continuar observando el comportamiento de DFS, nos alejamos un poco. Sacamos el tope de la pila, ahora hay cuatro estados expandidos y nueve en la frontera, dos a profundidad uno, dos a profundidad dos, dos a profundidad tres y tres a profundidad cuatro. Observamos que DFS avanza muy rápidamente con la profundidad. En tan solo cinco pasos, DFS alcanza la profundidad máxima de nuestro árbol de búsqueda. Ahora queda claro por qué el algoritmo se denomina búsqueda primero en profundidad. Veamos qué pasa ahora con el algoritmo de búsqueda primero en anchura. Comenzamos con el estado inicial. Sacamos el estado inicial y agregamos a los sucesores. El factor de ramificación tres nos da tres sucesores. Tres estados están en la frontera de búsqueda y uno en el conjunto de expandidos. En el siguiente paso, expandimos el estado al frente de la cola. Hasta este punto no hay diferencia en comportamiento con el algoritmo DFS. En el siguiente paso you observamos una diferencia, en la frontera ahora hay siete estados, uno a profundidad uno y seis a profundidad dos. Con la siguiente expansión, tenemos cuatro estados expandidos y nueve estados en la frontera. Apreciamos que todos los elementos en la frontera tienen una profundidad de dos, mientras que los estados expandidos tienen profundidad uno o cero. Si avanzamos a la expansión número 13, observamos el mismo patrón, todos los estados de la frontera son de profundidad tres y los expandidos de profundidades menores. Nos alejamos un poco. Observamos que BFS agota todas las posibilidades existentes a cierta profundidad antes de comenzar a expandir nodos de profundidades superiores. Sorprendentemente, tras 40 expansiones, todos los estados de la frontera tienen profundidad cuatro. Tenemos you 81 estados en la agenda. El consumo de memoria de BFS crece muy rápido con la profundidad. También entendemos por qué se le denomina algoritmo de búsqueda primero en anchura, dado que agota todas las posibilidades a cierta profundidad antes de avanzar a la profundidad siguiente. Bueno, llegó el momento de hacer el análisis asintótico de los algoritmos vistos. Vamos a evaluar cuatro aspectos, el primero es el consumo de memoria, el segundo es el tiempo que tarda en resolver el problema, el tercero es la calidad de la solución, si esta es óptima o no, y el cuatro es la completez del algoritmo, un algoritmo es completo si siempre entrega una respuesta. Bueno, comencemos con el análisis de memoria del algoritmo DFS. Vamos a observar cómo crece la frontera y el conjunto de expandidos, y para ello vamos a crear una tabla. En la primera columna vamos a poner el parámetro n, en la segunda el número de estados que están en la agenda o en la frontera, y en la tercera el número de estados que están en nuestro conjunto de expandidos. Comenzamos con profundidad n igual a cero. Aquà pues nada más tenemos el estado indicado en rojo, que es el estado inicial que está en la agenda. No tenemos ningún expandido. En la siguiente iteración, vamos a agregar a los sucesores del estado inicial. En este momento, you tenemos un estado en la lista de expandidos y tenemos a los sucesores de este estado en la agenda o en la frontera, estamos en profundidad uno. Ahora vamos a sacar el elemento que queda en el tope de la pila. Este elemento se expande y se agrega a la lista o al conjunto de expandidos. Tenemos sus tres sucesores que se agregan a la agenda. En este momento, el número de expandidos es dos y tenemos cinco elementos en la agenda, estamos a profundidad dos. Tomamos el elemento que está en el tope de la pila. Vamos a expandirlo, lo agregamos al conjunto de expandidos. Va a agregar tres sucesores. En al agenda ahora tenemos siete nodos indicados en rojo. Estamos en profundidad tres. Podemos continuar este proceso y lo que observamos es que cada vez que expandimos un nodo se agregan nodos que están a una profundidad mayor. La agenda crece de manera lineal con la expresión bn- (n- 1), mientras que el número de expandidos parece crecer a razón de n, la profundidad a la que nos encontramos. Sin embargo, en un grafo finito, esto es incorrecto. Por el momento vamos a considerar que la memoria crece de manera lineal a razón b de n y más adelante vamos a corregir este error. El siguiente elemento a evaluar va a ser el tiempo que le toma al algoritmo resolver el problema. Para ello, vamos a partir del estado en el que nos encontramos. Recordemos que en el análisis asintótico, cuando utilizamos la O grande lo que estamos analizando o tratando de acotar es el peor de los escenarios, es decir, en este caso, el tiempo máximo que se va a tardar el algoritmo. El peor de los escenarios es que la meta está en la última rama del árbol de búsqueda a una profundidad d. Vamos a continuar, entonces, a partir de donde nos quedamos. Tomamos el elemento en el tope de la pila y lo agregamos a la lista de expandimos. Aquà you hemos alcanzado la profundidad del árbol, por lo tanto no va a generar ningún hijo. Continuamos, sucede lo mismo, y con el siguiente va a pasar algo similar. Observamos que tras alcanzar la profundidad máxima el algoritmo va a retroceder, pues you no hay nodos sucesores. Esto va a resultar en un crecimiento no monotónico con las iteraciones. Aquà en el diagrama hemos ilustrado cómo se da esta sucesión. El algoritmo llega hasta la profundidad máxima y después empieza a retroceder. Vuelve a aumentar la profundidad, retrocede y luego retrocede más aún hasta llegar a los hijos del estado inicial y vuelve nuevamente a avanzar, alcanza la profundidad máxima y retrocede. Estas oscilaciones hacen que cambie la profundidad de los vértices que se están expandiendo. Ahora sà vamos a regresar a corregir la asignación de memoria que habÃamos hecho. Dijimos que crecÃa de manera lineal. Sin embargo, si observamos el diagrama, vemos que en la lista de expandidos van a estar prácticamente todos los nodos del árbol. Es decir, que en realidad, si consideramos tanto la agenda como los nodos expandidos, el crecimiento de memoria con la profundidad es exponencial. En este caso, b a la m. Respecto del parámetro del tiempo, observamos que está emparejado con el consumo de memoria. Para cada expansión, necesitamos una iteración. Es decir, tanto el tiempo como la memoria crecerán exponencialmente con el parámetro m, que dijimos que era la longitud más larga entre dos vértices en el grafo. El siguiente parámetro que vamos a considerar es la calidad de la solución. Aquà entendida como si la solución es óptima en el número de pasos desde el estado inicial. En un ejemplo que you trabajamos en el pizarrón, observamos que el algoritmo no nos entrega la solución óptima. De hecho, como el algoritmo avanza muy rápido con la profundidad, es muy probable que la solución que encuentre sea una trayectoria muy larga. El último aspecto que vamos a analizar es la completez. El algoritmo DFS no es completo si el grafo es infinito. Aquà podemos ver cómo el algoritmo toma una dirección de búsqueda y continúa por esa dirección. A pesar de que la solución pudiera estar relativamente cercana al estado inicial, el algoritmo jamás regresará. Si el grafo es finito, el algoritmo eventualmente tendrá que encontrar la solución, pero esto solo es cierto de manera teórica. En la práctica, en grafos grandes, el algoritmo nunca regresará o consumirá todos los recursos computacionales. Tras terminar el análisis del algoritmo DFS, observamos lo siguiente, consume mucha memoria, tarda mucho tiempo y, cuando encuentra una solución, esta no es muy buena. Bueno, esto podrÃa sugerir que el algoritmo es poco efectivo. Sin embargo, hay algo muy interesante con este algoritmo, el crecimiento que tiene la agenda respecto de la profundidad es lineal. Lo que está minando el desempeño del algoritmo es nuestro conjunto de expandidos. Si de alguna manera pudiéramos quitar ese conjunto, el algoritmo podrÃa ser bastante interesante. Más adelante en el curso vamos a ver cómo hacerlo. Comencemos el análisis asintótico del algoritmo BFS. El primer aspecto, la memoria. Comenzamos con el estado inicial, tenemos un estado en la agenda. Lo sacamos, agregamos los tres sucesores, ahora hay tres estados en la agenda y uno en la lista de expandidos. En el siguiente paso, tomamos el elemento que está al frente de la cola y lo expandimos. Tomamos el siguiente, lo expandimos, y nuevamente lo expandimos hasta completar todos los nodos a profundidad dos. Aquà observamos que tenemos nueve estados en la agenda y cuatro en la lista de expandidos. A diferencia del algoritmo DFS, la profundidad de los nodos que se van descubriendo crece monótonamente. Bueno, you podemos identificar entonces que el consumo de memoria va a ser exponencial con la profundidad de la solución. El siguiente aspecto a analizar va a ser el tiempo. El tiempo y la memoria crecen a la par. También va a ser exponencial con la profundidad de la solución, el parámetro D. Respecto de la calidad de la solución, puesto que el algoritmo expande todos los nodos que están a cierta profundidad antes de expandirlos de la profundidad siguiente, el algoritmo se va a encontrar a la solución a la profundidad mÃnima. Es decir, este algoritmo nos regresa siempre la solución óptima en número de pasos. Respecto de la completez, el algoritmo BFS encontrará la solución sujeto a que disponga de los recursos computacionales suficientes. Hemos terminado el análisis asintótico del algoritmo BFS. Respecto de la memoria, BFS consume muchos recursos. Vimos que su crecimiento es exponencial con la profundidad. Respecto del tiempo, también crece exponencialmente, pero está acotado, en ambos casos, por la profundidad de la solución. Si la solución está suficientemente cerca, BFS puede ser un algoritmo efectivo. Respecto de la calidad de la solución, observamos también que puesto que agota todas las posibilidades que están a cierta profundidad antes de comenzar con la profundidad siguiente, se va a encontrar a la solución a la profundidad de longitud mÃnima. Es decir, el algoritmo es bueno, pues nos da la solución óptima. Y respecto de la completez, teóricamente, en un grafo finito, el algoritmo es completo. Sin embargo, como el crecimiento es exponencial en memorial y en tiempo, es probable que en la mayorÃa de las aplicaciones consuma todos los recursos computacionales de que dispone. [MÚSICA] [MÚSICA]
