Ir al contenido principal

BÚSQUEDA BIDIRECCIONAL


Búsqueda Bidireccional
Esta es una búsqueda que avanza a partir del estado inicial y que retrocede a partir de la meta y que se detiene cuando ambas búsquedas se detienen en algún punto intermedio.
En esta búsqueda el tiempo y el espacio requerido en memoria crecen exponencialmente con respecto a la mitad de la profundidad (bd/2).Es óptima y completa.
Búsquedas No Informadas - Fernando Sancho Caparrini

Funcionamiento
Se realizan dos búsquedas simultáneas: una desde el estado inicial hasta el estado final, y otra desde el estado final hasta el estado inicial.
La búsqueda global acaba cuando ambas búsquedas parciales se encuentran.

Condiciones para su uso
Para que se pueda realizar este tipo de búsqueda se tienen que cumplir dos condiciones:
–  Los operadores han de ser reversibles
–  Que la meta sea explícita

Características
–  Se llevan a la vez dos búsquedas
–  Al menos una de estas dos búsquedas debe ser en anchura
–  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 inicial y el meta.

Ventaja y desventaja
Ventajas y desventajas del e-learning - ElerniamLa ventaja de esta búsqueda es que reduce a la mitad el factor exponencial del costo computacional con respecto a la búsqueda en amplitud, siendo a su vez, la principal desventaja desde el punto de vista del costo de almacenamiento.

Variante: Búsqueda dirigida por islas
Como variante de este método, existe la búsqueda dirigida por islas, que es una generalización del BB en el que se establecen un conjunto de objetivos intermedios (islas), lo que suele reducir un problema de búsqueda grande en un conjunto de problemas de búsqueda menores.
Si se van espaciando estas islas entre el nodo origen y el objetivo, se puede conseguir que su complejidad mejore.
Las cotas decrecen, pero suele ser difícil garantizar la optimalidad, ya que habría que asegurar que todas las islas (u objetivos intermedios) están en el camino óptimo de la solución original.




Fuente
–  Caparrini,F. (2016). Búsquedas No Informadas. abril 22,2020, de DISQUS Sitio web: http://www.cs.us.es/~fsancho/?e=95
–  Arnaudo,Juan Pablo. (2013). Búsqueda bidireccional. abril 22,2020, de Prezi Sitio web: https://prezi.com/pb03fk2kvm4f/busqueda-bidireccional/

Comentarios