Búsqueda en profundidad progresiva y búsqueda bidireccional
PREGUNTA:
El apartado que menos tengo claro es de la búsqueda en profundidad
progresiva y la bidireccional.
RESPUESTA:
En la búsqueda en profundidad siempre se intenta bajar de nivel. En
el momento en que no podamos hacerlo subimos a aquel nodo que nos
permita seguir bajando de nivel. Para poder hacer esto se utiliza
un estructura tipo pila. En el libro de problemas aparecen varios
problemas tipo de este algoritmo. La búsqueda en profundidad
progresiva consiste en repetir una búsqueda en profundidad,
aumentando de uno en uno el límite de profundidad con que se realiza
la búsqueda en profundidad anterior.
En la búsqueda bidireccional se llevan a la vez dos búsquedas: una
descendente desde el 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 ascencente y descendente puedan encontrarse
en algún momento. (Ten en 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úsqueda bidireccional.). Por lo
demás este método no tiene ninguna dificultad: simplemente,
por ejemplo, puedes realizar un búsqueda descendente del
nodo meta en anchura y una búsqueda ascendente del nodo
inicial en profundidad, 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. El camino 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. En el libro de problemas hay un problema (el de los
cántaros) que aborda este tipo de búsqueda.