La búsqueda primero en amplitud ( BFS ) es un algoritmo para buscar una estructura de datos de árbol para un nodo que satisfaga una propiedad determinada. Comienza en la raíz del árbol y explora todos los nodos en la profundidad actual antes de pasar a los nodos del siguiente nivel de profundidad. Se necesita memoria adicional, generalmente una cola , para realizar un seguimiento de los nodos secundarios que se encontraron pero que aún no se exploraron.
Clase | Algoritmo de búsqueda |
---|---|
Estructura de datos | Grafico |
Rendimiento en el peor de los casos | |
Complejidad espacial en el peor de los casos |
Por ejemplo, en un final de ajedrez, un motor de ajedrez puede construir el árbol del juego desde la posición actual aplicando todos los movimientos posibles y usar la búsqueda en amplitud para encontrar una posición ganadora para las blancas. Los árboles implícitos (como árboles de juegos u otros árboles de resolución de problemas) pueden tener un tamaño infinito; Se garantiza que la búsqueda en amplitud encuentre un nodo de solución [1] si existe.
En contraste, la búsqueda (simple) en profundidad , que explora la rama del nodo tanto como sea posible antes de retroceder y expandir otros nodos, [2] puede perderse en una rama infinita y nunca llegar al nodo de solución. La búsqueda iterativa de profundización primero en profundidad evita el último inconveniente al precio de explorar las partes superiores del árbol una y otra vez. Por otro lado, ambos algoritmos de profundidad se llevan bien sin memoria adicional.
La búsqueda en amplitud primero se puede generalizar a gráficos , cuando el nodo de inicio (a veces denominado "clave de búsqueda") [3] se da explícitamente y se toman precauciones después de un vértice dos veces.
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. [4] Fue reinventado en 1959 por Edward F. Moore , quien lo usó para encontrar el camino más corto fuera de un laberinto, [5] [6] y más tarde desarrollado por CY Lee en un algoritmo de enrutamiento de cables (publicado en 1961). [7]
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 [8]
1 procedimiento BFS ( G , root ) es 2 sea Q una cola 3 etiqueta la raíz como explorada 4 Q .enqueue ( raíz ) 5 mientras Q no esté vacío haga 6 v : = Q .dequeue () 7 si v es el objetivo, entonces 8 devuelve v 9 para todos los bordes de v a w en G. AdyacenteBordes ( v ) haga 10 si w no está etiquetado como explorado, entonces 11 etiqueta w como explorado12 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 explorado un vértice antes de poner en cola el vértice en lugar de retrasar esta comprobación hasta que el vértice se retira 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. [9]
La cola Q contiene la frontera a lo largo de la cual el algoritmo está buscando actualmente.
Los nodos se pueden etiquetar como explorados 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. [10]
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). [11] : 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. [12]
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 ) [13]
- (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 .
- Implementación de algoritmos paralelos para calcular el cierre transitivo de un gráfico. [14]
Ver también
- Búsqueda en profundidad
- Búsqueda iterativa que profundiza primero en profundidad
- Estructura de nivel
- Búsqueda lexicográfica en amplitud primero
- Búsqueda paralela en amplitud
Referencias
- ^ es decir, un nodo que satisface la propiedad especificada
- ^ Cormen Thomas H .; et al. (2009). "22,3". Introducción a los algoritmos . Prensa del MIT.
- ^ "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 .
- ^ 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.
- ^ Dhulipala, Laxman; Blelloch, Guy E .; Shun, Julian (21 de agosto de 2019). Los algoritmos de gráficos paralelos teóricamente eficientes pueden ser rápidos y escalables . pag. 17. arXiv : 1805.05208 . doi : 10.1145 / 3210377.3210414 . ISBN 9781450357999. S2CID 44126609 .
- 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