Hoy vamos a presentar una modificación del algoritmo de búsqueda primero en anchura. El algoritmo se denomina búsqueda bidireccional. [MÚSICA] Para poder aplicar la búsqueda bidireccional vamos a requerir restringir un poco más las caracterÃsticas del problema. La primera restricción es que debemos conocer el estado meta u objetivo. Si no conocemos el estado meta o existe más de un objetivo, no podemos aplicar el algoritmo como se va a presentar. La segunda condición es que podamos determinar el conjunto de estados de los que es sucesor bajo la aplicación de las acciones. El algoritmo bidireccional es en realidad dos búsquedas que se alternan. Estas búsquedas podrÃan realizarse en paralelo pero habrÃa que modificar ligeramente el algoritmo que vamos a presentar. La primera de las búsquedas es una búsqueda progresiva o hacia adelante comenzando del estado inicial. La segunda es una búsqueda regresiva o hacia atrás empezando en el estado meta. El objetivo de ambas búsquedas es que se encuentren en un punto a la mitad. Si encontramos un estado que pertenece a ambas fronteras podemos recuperar la ruta. Vamos a ilustrar cómo funciona el algoritmo de búsqueda bidireccional. El estado inicial se agrega a la frontera de búsqueda progresiva, el estado meta se agrega a la frontera de la búsqueda regresiva. La búsqueda progresiva expande el nodo inicial. La nueva frontera son todos los estados a profundidad 1. La búsqueda progresiva busca que su frontera se intercepte con la frontera de la búsqueda regresiva, esto no ha pasado aún. Ahora es el turno de la búsqueda regresiva. Si hacemos las búsquedas por turnos garantizamos que al interceptarse las fronteras tendremos la solución óptima. La búsqueda regresiva expande el estado meta. Turno de la búsqueda progresiva, generamos la frontera actual, todos los sucesores de los estados de la frontera anterior. Ahora es el turno de la búsqueda regresiva, agregamos todos los estados a profundidad 2, aún no se interceptan las fronteras. Hacia adelante con profundidad 3, hacia atrás con profundidad 3, se alcanza profundidad 4 en la búsqueda progresiva, no hay intersección todavÃa, la búsqueda regresiva también alcanza profundidad 4 sin intersección. Turno de la búsqueda hacia adelante. No mostramos todos los nodos a profundidad 5, únicamente el nodo de intersección entre las dos fronteras. Considerando que la intersección se encuentra tras expandir todos los estados a profundidad 5 en la frontera de la búsqueda progresiva, y sumando el total de estados expandidos con el total de ambas fronteras, tenemos que hemos expandido poco menos de 500 estados. Dado que en este ejemplo la solución está a profundidad 9, un algoritmo BFS convencional habrÃa expandido cerca de 30000 estados para encontrar la solución, esto es un ahorro significativo en memoria. [SONIDO] Vamos a presentar el algoritmo bidireccional. El algoritmo tiene dos entradas, el estado inicial S cero y el estado meta. Aquà you vemos la primera diferencia, no podemos tener una función de paro porque para poder aplicar este algoritmo necesitamos conocer estrictamente este estado. El primer paso es verificar la condición trivial. Si el estado inicial es igual al estado meta, you terminamos. El paso siguiente es inicializar las fronteras de búsqueda. En este algoritmo tenemos dos fronteras, la frontera para la búsqueda hacia adelante o progresiva, y la frontera para la búsqueda hacia atrás o regresiva. Como necesitamos verificar para cada expansión de nodo la pertenencia de ese nodo a cada una de estas fronteras, necesitamos que esa operación sea muy rápida. La estructura de datos ideal aquà se llama tabla de dispersión o, en inglés, hash table. La frontera que hacia adelante la denominamos P de progresivo y voy a denotar que voy a agregar aquà el estado inicial de esta forma. Esto lo que quiere decir es que la llave es el estado inicial y el valor es el estado inicial, es una auto asociación. Para regresivo, la frontera que va hacia atrás, vamos a agregar el estado meta, también auto asociado. El siguiente paso es entrar en un ciclo de iteración. Aquà vamos a considerar que mientras P y R tengan elementos. Vamos a necesitar dos fronteras temporales las cuales vamos a llamar P prima y R prima, las inicializamos vacÃas. Después lo que vamos a hacer es la expansión de la frontera que va hacia adelante, la frontera progresiva. Entonces, para eso vamos a sacar todos los elementos de P y vamos a agregar a sus sucesores. Pero antes vamos a verificar si hay una intersección con la frontera regresiva, esta es la condición de paro de nuestro algoritmo. Entonces preguntamos si el estado pertenece a la frontera que va hacia atrás. De ser asÃ, podemos recuperar la ruta. Vamos a recuperar la ruta en dos partes. La primera parte es la sub ruta del estado inicial al estado S y la segunda parte es la sub ruta del estado meta al estado S. Entonces vamos a hacer primero la sub ruta que va hacia adelante. Esta simplemente la obtenemos con nuestro procedimiento para ruta y con el estado S. Ahora, la sub ruta que va del estado meta al estado S la vamos a extraer de la siguiente manera, bueno, evidentemente no puedo usar S porque me va a dar la misma sub ruta, tengo que extraer el estado S que está en la frontera regresiva. Eso lo hago asÃ. Entonces aquà estamos utilizando como llave el estado S pero el valor va a ser el estado asociado en la frontera regresiva, el cual trae toda la secuencia necesaria para llegar al estado meta. Bueno, finalmente vamos a juntar las dos sub rutas, pero esta viene invertida, entonces tenemos que invertir el orden para que quede bien. Invertimos la ruta que está en b. Ahora sà vamos a regresar la concatenación de las vistas. Bueno, este es el caso en que haya una intersección, pero, ¿qué si no hay una intersección? Vamos a expandir el nodo siempre que no se haya expandido, entonces aquà también tenemos la lista de expandidos o el conjunto de expandidos y vamos a verificar contra ese conjunto el cual voy a llamar X. Si S no está en el conjunto de expandidos entonces lo vamos a agregar a ese conjunto. [SONIDO] [AUDIO_EN_BLANCO] Y lo siguiente es agregar el estado S a nuestra variable temporal que tenemos aquÃ, que va hacia adelante, que es P prima. Recordemos que es una tabla de dispersión, hacemos la auto asociación, y bueno, una vez que terminamos de expandir todos los nodos, vamos a actualizar P con P prima. Todo este bloque que hemos escrito es la expansión de la frontera hacia adelante, es la parte progresiva. Ahora vamos a hacer el bloque correspondiente a la expansión regresiva. Ahora S, los estados S, los vamos a sacar no de P sino de R, de la frontera que viene hacia atrás, y aquà vamos a verificar si hay una intersección con la frontera que viene hacia adelante, o sea con P. Si hay una intersección, vamos a extraer la parte que va hacia adelante de la siguiente manera. Como S pertenece a la frontera que va hacia atrás, aquà tenemos que usar la tabla de dispersión para extraer la auto asociación en la frontera que va hacia adelante o la progresiva, entonces eso lo vamos a hacer asÃ. Ahora vamos a extraer la sub ruta que viene del estado meta. Aquà como estamos en la frontera hacia atrás, pues no tenemos que usar el diccionario. Nuevamente, como b viene de la meta, hay que invertir el orden, y vamos a regresar la ruta que es la concatenación de los dos. Bueno, si no hay una intersección, vamos a hacer algo similar a lo que tenemos acá, también la lista de expandidos puede ser común, vamos a considerar que asà es, si no pertenece a X entonces lo vamos a agregar en X y vamos a actualizar nuestra frontera temporal R prima agregando este elemento, la auto asociación del elemento. Este es nuestro ciclo para la expansión de la frontera. Al terminar, pues tenemos que actualizar R con R prima. Este bloque que acabamos de escribir es la búsqueda regresiva. Finalmente, también puede darse el caso de que no exista una ruta entre el estado inicial y el estado meta, en ese caso, la última lÃnea del algoritmo es return none, o no hay solución. [SONIDO] Vamos a analizar el desempeño del algoritmo bidireccional. El primer aspecto a considerar es la memoria. En el algoritmo bidireccional dividimos la búsqueda en dos sub búsquedas. Lo que ganamos es que ahora la longitud de cada una de ellas es la mitad de la profundidad a la que se encuentra la meta. Este es un ahorro sustancial de memoria, significa que, en este caso, el algoritmo es O b elevado a la d/2. El siguiente aspecto que vamos a considerar es el tiempo, y el tiempo está a la par del consumo de memoria, esto es O b elevado a la d/2. Respecto de la calidad de la solución, este algoritmo nos encuentra la solución óptima, y es también un algoritmo completo. Podemos considerar que el algoritmo bidireccional comparado con el algoritmo BFS es mejor. Sin embargo, hay que recordar que restringimos el tipo de problemas a los que se puede aplicar. Necesitamos conocer el estado meta y además necesitamos conocer, para cada estado, sus predecesores. [MÚSICA] [MÚSICA]
