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.
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
La 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
Publicar un comentario