Respuesta

28

¿Cómo funciona Bi-direccional BFS?

Ejecute simultáneamente dos BFS desde los vértices fuente y destino, terminando una vez que se descubra un vértice común a ambas ejecuciones. Este vértice estará a medio camino entre la fuente y el objetivo.

¿Por qué es mejor que BFS?

BFS bidireccional producirá resultados mucho mejores que BFS simple en la mayoría de los casos. Suponga que la distancia entre el origen y el destino es k, y el factor de bifurcación es B (cada vértice tiene en promedio bordes B).

  • BFS atravesará 1 + B + B^2 + ... + B^k vértices.
  • BFS bidireccional atravesará 2 + 2B^2 + ... + 2B^(k/2) vértices.

Para grandes B y k, el segundo es obviamente mucho más rápido que el primero.


En su caso:

Por simplicidad voy a asumir que no hay obstáculos en la matriz. Esto es lo que sucede:

iteration 0 (init): 
front1 = { (0,5) } 
front2 = { (4,1) } 

iteration 1: 
front1 = { (0,4), (1,5) } 
front2 = { (4,0), (4,2), (3,1), (5,1) } 

iteration 2: 
front1 = { (0,3), (1,4), (2,5) } 
front2 = { (3,0), (5,0), (4,3), (5,2), (3,2), (2,1) } 

iteration 3: 
front1 = { (0,2), (1,3), (2,4), (3,5) } 
front2 = { (2,0), (4,4), (3,3), (5,3), (2,2), (1,1), } 

iteration 4: 
front1 = { (0,1), (1,2), .... } 
front2 = { (1,2) , .... } 

Ahora, hemos descubierto que los frentes se cruzan en (1,2), junto con los caminos seguidos para llegar desde los vértices de origen y destino:

path1: (0,5) -> (0,4) -> (0,3) -> (0,2) -> (1,2) 
path2: (4,1) -> (3,1) -> (2,1) -> (1,1) -> (1,2) 

Ahora solo necesitamos invertir la ruta 2 y anexarla a la ruta 1 (eliminando uno de los vértices de intersección comunes, por supuesto), para darnos nuestra ruta completa:

(0,5) -> (0,4) -> (0,3) -> (0,2) -> (1,2) -> (1,1) -> (2,1) -> (3,1) -> (4,1) 
+1

Buena explicación. ¿Te preguntas cómo almacenarías todos los caminos para rastrear cuando hay una intersección entre las colas? Tomaría mucho espacio para cada nodo si almacenamos todas las rutas. –

+0

@newbie_old [Similar a BFS normal] (http://stackoverflow.com/q/9590299/572670), cada nodo que descubres, marcas cómo lo descubres. (En el cuidado especial BFS bidireccional para el nodo intersecante que debe tener dos padres). Luego, regresas del nodo hasta la raíz. El requisito de espacio es lineal en el número de vértices, que es el espacio requerido para BFS de todos modos (para el conjunto 'visitado' y para la cola). – amit

+0

Entonces la complejidad del tiempo se reduce por raíz cuadrada; mientras que la complejidad del espacio es la misma? – user815408

Cuestiones relacionadas