La búsqueda primero en amplitud ( BFS ) es un algoritmo para recorrer o buscar estructuras de datos de árbol o gráfico . Comienza en la raíz del árbol (o algún nodo arbitrario de un gráfico, a veces denominado "clave de búsqueda" [1] ), y explora todos los nodos vecinos en la profundidad actual antes de pasar a los nodos del siguiente nivel de profundidad.
Clase | Algoritmo de búsqueda |
---|---|
Estructura de datos | Grafico |
Rendimiento en el peor de los casos | |
Complejidad espacial en el peor de los casos |
Utiliza la estrategia opuesta de la búsqueda en profundidad , que en su lugar explora la rama del nodo en la medida de lo posible antes de verse obligado a retroceder y expandir otros nodos. [2]
BFS y su aplicación para encontrar componentes conectados de gráficos fueron inventados en 1945 por Konrad Zuse , en su (rechazado) Ph.D. tesis sobre el lenguaje de programación Plankalkül , pero esto no se publicó hasta 1972. [3] Fue reinventado en 1959 por Edward F. Moore , quien lo usó para encontrar el camino más corto fuera de un laberinto, [4] [5] y más tarde desarrollado por CY Lee en un algoritmo de enrutamiento de cables (publicado en 1961). [6]
Pseudocódigo
Entrada : un gráfico G y una raíz de vértice inicial de G
Salida : Estado objetivo. Los enlaces principales rastrean la ruta más corta hasta la raíz [7]
1 procedimiento BFS ( G , root ) es 2 sea Q una cola 3 etiquetar la raíz como descubierta 4 Q .enqueue ( raíz ) 5 mientras Q no esté vacío haga 6 v : = Q .dequeue () 7 si v es la meta a continuación, 8 de retorno v 9 para todos los bordes de v a w en G .adjacentEdges ( v ) hacer 10 si w no se etiqueta como descubierto entonces 11 etiqueta w como descubierto12 Q .enqueue ( w )
Más detalles
Esta implementación no recursiva es similar a la implementación no recursiva de la búsqueda en profundidad , pero se diferencia de ella de dos maneras:
- utiliza una cola (primero en entrar, primero en salir) en lugar de una pila y
- comprueba si se ha descubierto un vértice antes de poner en cola el vértice en lugar de retrasar esta comprobación hasta que el vértice se retire de la cola.
Si G es un árbol , reemplazar la cola de este algoritmo de búsqueda en amplitud con una pila producirá un algoritmo de búsqueda en profundidad. Para gráficos generales, reemplazar la pila de la implementación iterativa de búsqueda en profundidad primero con una cola también produciría un algoritmo de búsqueda en amplitud, aunque algo no estándar. [8]
La cola Q contiene la frontera a lo largo de la cual el algoritmo está buscando actualmente.
Los nodos se pueden etiquetar como descubiertos almacenándolos en un conjunto o mediante un atributo en cada nodo, según la implementación.
Tenga en cuenta que la palabra nodo suele ser intercambiable con la palabra vértice .
El atributo padre de cada nodo es útil para acceder a los nodos en una ruta más corta, por ejemplo, retrocediendo desde el nodo de destino hasta el nodo inicial, una vez que se ha ejecutado el BFS y se han establecido los nodos predecesores.
La búsqueda primero en amplitud produce un árbol llamado primero en amplitud . Puede ver cómo se ve un primer árbol de ancho en el siguiente ejemplo.
Ejemplo
El siguiente es un ejemplo del árbol de amplitud que se obtiene al ejecutar un BFS en ciudades alemanas a partir de Frankfurt :
Análisis
Complejidad temporal y espacial
La complejidad del tiempo se puede expresar como, ya que cada vértice y cada borde se explorarán en el peor de los casos. es el número de vértices y es el número de aristas del gráfico. Tenga en cuenta que puede variar entre y , dependiendo de lo escaso que sea el gráfico de entrada. [9]
Cuando se conoce de antemano el número de vértices del gráfico y se utilizan estructuras de datos adicionales para determinar qué vértices ya se han agregado a la cola, la complejidad del espacio se puede expresar como, dónde es el número de vértices. Esto se suma al espacio requerido para el gráfico en sí, que puede variar según la representación del gráfico utilizada por una implementación del algoritmo.
Cuando se trabaja con gráficos que son demasiado grandes para almacenarlos explícitamente (o infinitos), es más práctico describir la complejidad de la búsqueda en amplitud en diferentes términos: para encontrar los nodos que están a una distancia d del nodo de inicio (medidos en número de recorridos de borde), BFS toma O ( b d + 1 ) tiempo y memoria, donde b es el " factor de ramificación " del gráfico (el grado medio de salida). [10] : 81
Lo completo
En el análisis de algoritmos, la entrada a la búsqueda en amplitud primero se supone que es un gráfico finito, representada explícitamente como una lista de adyacencia , matriz de adyacencia , o representación similar. Sin embargo, en la aplicación de métodos de recorrido de grafos en inteligencia artificial, la entrada puede ser una representación implícita de un grafo infinito. En este contexto, un método de búsqueda se describe como completo si se garantiza que encontrará un estado objetivo, si existe. La búsqueda primero en amplitud está completa, pero la búsqueda en profundidad no lo está. Cuando se aplica a gráficos infinitos representados implícitamente, la búsqueda primero en amplitud eventualmente encontrará el estado objetivo, pero la búsqueda en profundidad primero puede perderse en partes del gráfico que no tienen un estado objetivo y nunca regresan. [11]
Pedido de BFS
Se dice que una enumeración de los vértices de un gráfico es una ordenación BFS si es el resultado posible de la aplicación de BFS a este gráfico.
Dejar ser un gráfico con vértices. Recordar que es el conjunto de vecinos de . Dejar ser una lista de elementos distintos de , por , dejar ser el menos tal que es vecino de , si tal existe y ser de lo contrario.
Dejar ser una enumeración de los vértices de . La enumeración se dice que es un pedido BFS (con fuente ) si, para todos , es el vértice tal que es mínimo. Equivalentemente, es un pedido BFS si, para todos con , existe un vecino de tal que .
Aplicaciones
La búsqueda en amplitud se puede utilizar para resolver muchos problemas en la teoría de grafos, por ejemplo:
- Copiando la recolección de basura , el algoritmo de Cheney
- Encontrar la ruta más corta entre dos nodos u y v , con la longitud de la ruta medida por el número de bordes (una ventaja sobre la búsqueda en profundidad ) [12]
- (Inversa) Numeración de malla de Cuthill-McKee
- Método de Ford-Fulkerson para calcular el flujo máximo en una red de flujo
- La serialización / deserialización de un árbol binario frente a la serialización en orden ordenado permite reconstruir el árbol de manera eficiente.
- Construcción de la función de falla del comparador de patrones Aho-Corasick .
- Prueba de la bipartición de un gráfico .
Ver también
- Búsqueda en profundidad
- Búsqueda iterativa que profundiza primero en profundidad
- Estructura de niveles
- Búsqueda lexicográfica en amplitud primero
- Búsqueda paralela en amplitud
Referencias
- ^ "Especificación de referencia Graph500 (evaluación del rendimiento de supercomputadora)" . Graph500.org, 2010. Archivado desde el original el 26 de marzo de 2015 . Consultado el 15 de marzo de 2015 .
- ^ Cormen Thomas H .; et al. (2009). "22,3". Introducción a los algoritmos . Prensa del MIT.
- ^ Zuse, Konrad (1972), Der Plankalkül (en alemán), Konrad Zuse Internet Archive. Consulte las páginas 96-105 del archivo pdf vinculado (numeración interna 2.47-2.56).
- ^ Moore, Edward F. (1959). "El camino más corto a través de un laberinto". Actas del Simposio internacional sobre la teoría de la conmutación . Prensa de la Universidad de Harvard. págs. 285-292. Según lo citado por Cormen, Leiserson, Rivest y Stein.
- ^ Skiena, Steven (2008). "Ordenar y buscar". El Manual de diseño de algoritmos . Saltador. pag. 480. bibcode : 2008adm..book ..... S . doi : 10.1007 / 978-1-84800-070-4_4 . ISBN 978-1-84800-069-8.
- ^ Lee, CY (1961). "Un algoritmo para conexiones de ruta y sus aplicaciones". Transacciones IRE en computadoras electrónicas . doi : 10.1109 / TEC.1961.5219222 .
- ^ Cormen, Thomas H. "22.2 Búsqueda primero en amplitud". Introducción a los algoritmos . ISBN 978-81-203-4007-7. OCLC 1006880283 .
- ^ "Recorrido de gráfico basado en pila ≠ primera búsqueda en profundidad" . 11011110.github.io . Consultado el 10 de junio de 2020 .
- ^ Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001) [1990]. "22.2 Búsqueda primero en amplitud". Introducción a los algoritmos (2ª ed.). MIT Press y McGraw-Hill. págs. 531–539. ISBN 0-262-03293-7.
- ^ Russell, Stuart ; Norvig, Peter (2003) [1995]. Inteligencia artificial: un enfoque moderno (2ª ed.). Prentice Hall. ISBN 978-0137903955.
- ^ Coppin, B. (2004). Inteligencia artificial iluminada. Jones y Bartlett Learning. págs. 79–80.
- ^ Aziz, Adnan; Prakash, Amit (2010). "4. Algoritmos sobre gráficos". Algoritmos para entrevistas . pag. 144. ISBN 978-1453792995.
- Knuth, Donald E. (1997), El arte de la programación informática Vol 1. 3ª ed. , Boston: Addison-Wesley, ISBN 978-0-201-89683-1
enlaces externos
- Estructuras de datos abiertos - Sección 12.3.1 - Búsqueda en amplitud primero , Pat Morin
- Búsqueda simplificada en función de la amplitud