← inteligencia-artificial
24. algoritmo de búsqueda bidireccional
El algoritmo de búsqueda bidireccional es una técnica de búsqueda en grafos que explora simultáneamente desde el estado inicial y desde el estado meta, con el objetivo de que ambas búsquedas se encuentren en algún punto intermedio. Se utiliza principalmente para reducir drásticamente el costo computacional de encontrar una solución.
Idea fundamental
En lugar de buscar desde el inicio hasta la meta en una sola dirección, el algoritmo realiza dos búsquedas:
- Una búsqueda hacia adelante desde el estado inicial.
- Una búsqueda hacia atrás desde el estado objetivo.
Cuando ambas búsquedas se intersectan, se reconstruye el camino completo uniendo las dos mitades.
¿Por qué es eficiente?
Si el branching factor es bbb y la profundidad de la solución es ddd:
- Una búsqueda tradicional (como BFS) cuesta
- La búsqueda bidireccional reduce el costo a aproximadamente: