¿Cómo se usa un BFS bidireccional para encontrar la ruta más corta? Digamos que hay una cuadrícula de 6x6. El punto de inicio está en (0,5) y el punto final está en (4,1). ¿Cuál es el camino más corto usando bfs bidireccionales? No hay costos de ruta. Y no está dirigido.¿Cómo se usa un BFS bidireccional para encontrar la ruta más corta?
Respuesta
¿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. Algoritmo para encontrar la ruta más corta, con obstáculos
- 2. ¿Cómo puedo encontrar la ruta real encontrada por BFS?
- 3. Encontrar la ruta globalmente más corta en trapezoides no degeneradas
- 4. Encontrar la ruta más corta usando el algoritmo de Dijkstra
- 5. Búsqueda eficiente de la ruta más corta en gráficos grandes
- 6. Networkx - Longitud de ruta más corta
- 7. Encontrar la ruta más corta entre dos nodos pertenecientes a dos subconjuntos disjuntos de un gráfico
- 8. Algún algoritmo para encontrar la ruta/distancia más corta en Android?
- 9. Ruta más corta en ausencia del borde dado
- 10. Ruta más corta (menos nodos) para gráficos no ponderados
- 11. Encontrar la ruta más corta entre dos puntos en una cuadrícula, usando Haskell
- 12. cadena más corta dentro de la misma ruta (rama)
- 13. ¿Cuáles son las aplicaciones del algoritmo de ruta más corta?
- 14. ¿Qué algoritmo puedo usar para encontrar la ruta más corta entre tipos de nodos especificados en un gráfico?
- 15. Algoritmo: ruta más corta entre todos los puntos
- 16. Ruta más corta de Java Maze 2d int array
- 17. ruta más corta utilizando el algoritmo de Dijkstra
- 18. ¿Cuál es el camino más rápido para encontrar la distancia más corta entre dos cartesiano polígonos
- 19. Ejemplo simple de bfs ... No lo entiendo
- 20. Optimización del algoritmo - Ruta más corta entre varios puntos
- 21. más corta Rubí Quine
- 22. ¿Cómo se usa SharedPreferences para guardar más de un valor?
- 23. Cómo implementar readlink para encontrar la ruta
- 24. ¿Longitud de la línea más corta?
- 25. ¿Por qué usar el algoritmo de Dijkstra si Breadth First Search (BFS) puede hacer lo mismo más rápido?
- 26. Cómo minimizar el costo total del árbol de ruta más corta
- 27. recorte uuid más para hacer cadena corta
- 28. Cómo encontrar la cadena más corta en una lista en Python
- 29. Por qué DFS y no BFS para encontrar el ciclo en gráficos
- 30. Dijkstra para la ruta más larga en un DAG
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. –
@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
Entonces la complejidad del tiempo se reduce por raíz cuadrada; mientras que la complejidad del espacio es la misma? – user815408