Búsqueda Bidireccional

Escuela:
Lic. En Sistemas Computacionales

Maestro:
Lamberto

Materia:
Algoritmos avanzados

BUSQUEDA BIDIRECCIONAL

El propósito de la búsqueda bidireccional es encontrar su objetivoen el menor tiempo posible y esto se logra haciendo dos búsquedas simultáneas de ahí que el nombre de bidireccional. En la búsqueda bidireccional se llevan a la vez dos búsquedas: una descendente desdeel nodo inicial y otra ascendente desde el nodo meta. Al menos una de estas dos búsquedas, debe ser en anchura para que el recorrido ascendente y descendente pueda encontrarse en algún momento. (Tenen cuenta que si tanto el recorrido descendente como el ascendente fueran en profundidad, podría pasar que nunca se cruzaran o encontraran, con lo cual no tendría sentido realizar la búsquedabidireccional.). Por lo demás este método no tiene ninguna dificultad: simplemente, por ejemplo, puedes realizar una búsqueda descendente del nodo meta en anchura y una búsqueda ascendente del nodo inicial enprofundidad, alternando la expansión de los nodos entre un tipo de búsqueda y el otro. Cuando se llegue a un nodo que ya había sido explorado con el otro tipo de búsqueda, el algoritmo acaba. Elcamino solución es la suma de los caminos hallados por cada búsqueda desde el nodo mencionado hasta el nodo inicial y hasta el nodo meta.
1. ¿Cómo funciona el algoritmo?
Esta búsqueda hace uso dedos búsquedas las cuales se las conoce como:
* Búsqueda a la ancho o hacia adelante (En el siguiente ejemplo tenemos como objetivo F)

  

 

Búsqueda hacia atrás: Aquí primeramenteexpandiremos los nodos hasta llegar a un nodo hoja, y a partir de ese nodo se empezara hacer las comparaciones. Y si el primer nodo hoja al que llegamos (al nodo que siempre llegaremos primero será el que seencuentra más a la izquierda) no es el nodo objetivo entonces comparamos con el nodo que está a su derecha, y si este tampoco es entonces se empieza hacer la búsqueda hacia atrás.

 
En este...