Tema
Búsqueda bidireccional
- IA clásica
- Nivel intermedio
La búsqueda bidireccional lanza dos frentes a la vez, uno desde el estado inicial hacia adelante y otro desde la meta hacia atrás, y se detiene cuando las dos fronteras se cruzan.
Nombre en inglés
Bidirectional search
Intuición
Dos círculos de radio d/2 abarcan mucho menos área que un solo círculo de radio d, y esa es toda la idea. Como el número de nodos crece de forma exponencial con la profundidad, partir el recorrido en dos mitades cambia b^d por dos veces b^{d/2}, que para b igual a 10 y d igual a 6 significa pasar de un millón de nodos a dos mil. El precio consiste en necesitar los predecesores de cada estado y en llevar dos estructuras de datos en paralelo.
Fórmula
coste unidireccional O(b^d) frente a coste bidireccional O(2 b^{d/2})
Ejemplo resuelto
Con b igual a 10 y la meta a 6 pasos, el frente hacia adelante explora 10 + 100 + 1000 = 1110 nodos hasta profundidad 3, y el frente hacia atrás explora otros 1110. La suma da 2220 nodos frente a los 1111110 que necesitaría la búsqueda en anchura hasta profundidad 6. El camino final se arma pegando la rama que va del inicio al nodo de encuentro con la rama invertida que va del nodo de encuentro a la meta.
Errores frecuentes
- Devolver el primer camino que aparece al cruzarse las fronteras y darlo por óptimo, cuando la condición correcta exige seguir hasta que el mejor camino encontrado no supere la suma de los menores costes pendientes en las dos fronteras.
- Aplicarla a un problema cuyos operadores no se pueden invertir, ya que sin predecesores no hay forma de expandir hacia atrás desde la meta.
- Usarla cuando la meta se define por una propiedad y no por un estado concreto, porque entonces el frente hacia atrás tendría que arrancar de un conjunto enorme de estados finales.
Ejercicio
Un espacio de estados tiene factor de ramificación 4 y la solución está a profundidad 8. Estima cuántos nodos se expanden en el peor nivel con búsqueda en anchura y con búsqueda bidireccional.
Ver la solución
La búsqueda en anchura llega al nivel 8 y expande del orden de 4^8 = 65536 nodos en ese nivel. La búsqueda bidireccional hace que cada frente llegue solo al nivel 4, con 4^4 = 256 nodos en el nivel más profundo de cada frente, y como hay dos frentes suman 512 nodos. La mejora es de un factor cercano a 128.
Respuesta: 65536 frente a 512.