Búsqueda en amplitud

Algoritmo para buscar los nodos de un gráfico.

Ejemplo animado de una búsqueda en amplitud. Negro: explorado, gris: en cola para ser explorado más adelante

BFS en algoritmo de resolución de laberintos

Parte superior del árbol del juego Tic-tac-toe

La búsqueda en amplitud ( BFS ) es un algoritmo para buscar en una estructura de datos de árbol 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 en el 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.

Por ejemplo, en un final de ajedrez , un motor de ajedrez puede construir el árbol de juego a partir de la posición actual aplicando todos los movimientos posibles y utilizando la búsqueda en amplitud para encontrar una posición ganadora para las blancas. Los árboles implícitos (como los á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 encontrará un nodo de solución ^[1], si existe.

Por el contrario, la búsqueda (simple) en profundidad (DFS), que explora la rama del nodo lo más lejos 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 en profundidad evita este último inconveniente al precio de explorar las partes superiores del árbol una y otra vez. Por otro lado, ambos algoritmos de profundidad suelen requerir mucha menos memoria adicional que la búsqueda de amplitud. ^[3]

La búsqueda en amplitud se puede generalizar tanto a gráficos no dirigidos como a gráficos dirigidos con un nodo de inicio determinado (a veces denominado "clave de búsqueda"). ^[4] En la búsqueda del espacio de estados en inteligencia artificial , a menudo se permiten búsquedas repetidas de vértices, mientras que en el análisis teórico de algoritmos basados ​​en la búsqueda en amplitud, generalmente se toman precauciones para evitar repeticiones.

BFS y su aplicación para encontrar componentes conectados de gráficos fueron inventados en 1945 por Konrad Zuse , en su (rechazado) doctorado. tesis sobre el lenguaje de programación Plankalkül , pero no se publicó hasta 1972. ^[5] Fue reinventado en 1959 por Edward F. Moore , quien lo utilizó para encontrar el camino más corto para salir de un laberinto, ^{[6] [7]} y posteriormente desarrollado por CY Lee en un algoritmo de enrutamiento de cables (publicado en 1961). ^[8]

Pseudocódigo

Entrada : un gráfico G y una raíz de vértice inicial de G

Salida : Estado objetivo. Los enlaces principales trazan el camino más corto hasta la raíz ^[9]

1 procedimiento BFS ( G , raíz ) es 2 sea Q una cola 3 etiqueta raíz explorada 4 Q .encolar ( 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 .adjacentEdges( v ) haz
10 si  w no está etiquetado como explorado entonces
11 etiqueta fue explorada12 w .parent := v
13 Q .encola( 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 en dos formas:

1. utiliza una cola ( primero en entrar, primero en salir ) en lugar de una pila (último en entrar, primero en salir) y
2. comprueba si un vértice ha sido explorado antes de ponerlo en cola en lugar de retrasar esta verificación hasta que el vértice sea retirado 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 con una cola también produciría un algoritmo de búsqueda en amplitud, aunque algo no estándar. ^[10]

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 principal de cada nodo es útil para acceder a los nodos en la 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 configurado los nodos predecesores.

La búsqueda en amplitud produce el llamado árbol en amplitud . Puede ver cómo se ve un árbol de ancho primero en el siguiente ejemplo.

Ejemplo

El siguiente es un ejemplo del árbol de amplitud obtenido al ejecutar un BFS en ciudades alemanas a partir de Frankfurt :

Un mapa de ejemplo del sur de Alemania con algunas conexiones entre ciudades.

El árbol de amplitud primero obtenido al ejecutar BFS en el mapa dado y comenzando en Frankfurt

Análisis

Complejidad temporal y espacial

La complejidad del tiempo se puede expresar como , ya que cada vértice y cada arista 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 qué tan escaso sea el gráfico de entrada. ^[11] ${\displaystyle O(|V|+|E|)}$ ${\displaystyle |V|}$ ${\displaystyle |E|}$ ${\displaystyle O(|E|)}$ ${\displaystyle O(1)}$ ${\displaystyle O(|V|^{2})}$

Cuando se conoce de antemano el número de vértices en el 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 , donde 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. ${\displaystyle O(|V|)}$ ${\displaystyle |V|}$

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: encontrar los nodos que están a la distancia d del nodo inicial (medido 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 de salida promedio). ^{[12] : 81}

Lo completo

En el análisis de algoritmos, se supone que la entrada a la búsqueda en amplitud es un gráfico finito, representado como una lista de adyacencia , una matriz de adyacencia o una representación similar. Sin embargo, en la aplicación de métodos de recorrido de gráficos en inteligencia artificial , la entrada puede ser una representación implícita de un gráfico infinito. En este contexto, un método de búsqueda se considera completo si se garantiza que encontrará un estado objetivo, si existe. La búsqueda en amplitud está completa, pero la búsqueda en profundidad no. Cuando se aplica a gráficos infinitos representados implícitamente, la búsqueda en amplitud eventualmente encontrará el estado objetivo, pero la búsqueda en profundidad puede perderse en partes del gráfico que no tienen un estado objetivo y nunca regresan. ^[13]

Pedido BFS

Se dice que una enumeración de los vértices de un gráfico es un ordenamiento BFS si es el posible resultado de la aplicación de BFS a este gráfico.

Sea un gráfico con vértices. Recuerde que es el conjunto de vecinos de . Sea una lista de elementos distintos de , para , sea el menos vecino de , si existe, y sea de otra manera. ${\displaystyle G=(V,E)}$ ${\displaystyle n}$ ${\displaystyle N(v)}$ ${\displaystyle v}$ ${\displaystyle \sigma =(v_{1},\dots ,v_{m})}$ ${\displaystyle V}$ ${\displaystyle v\in V\setminus \{v_{1},\dots ,v_{m}\}}$ ${\displaystyle \nu _{\sigma }(v)}$ ${\displaystyle i}$ ${\displaystyle v_{i}}$ ${\displaystyle v}$ ${\displaystyle i}$ ${\displaystyle \infty }$

Sea una enumeración de los vértices de . Se dice que la enumeración es un ordenamiento BFS (con fuente ) si, para todos , el vértice es mínimo . De manera equivalente, es un ordenamiento BFS si, para todo con , existe un vecino tal que . ${\displaystyle \sigma =(v_{1},\dots ,v_{n})}$ ${\displaystyle V}$ ${\displaystyle \sigma }$ ${\displaystyle v_{1}}$ ${\displaystyle 1<i\leq n}$ ${\displaystyle v_{i}}$ ${\displaystyle w\in V\setminus \{v_{1},\dots ,v_{i-1}\}}$ ${\displaystyle \nu _{(v_{1},\dots ,v_{i-1})}(w)}$ ${\displaystyle \sigma }$ ${\displaystyle 1\leq i<j<k\leq n}$ ${\displaystyle v_{i}\in N(v_{k})\setminus N(v_{j})}$ ${\displaystyle v_{m}}$ ${\displaystyle v_{j}}$ ${\displaystyle m<i}$

Aplicaciones

La búsqueda en amplitud se puede utilizar para resolver muchos problemas en teoría de grafos, por ejemplo:

• Copiar recolección de basura , algoritmo de Cheney
• Encontrar el camino más corto entre dos nodos u y v , con la longitud del camino medida por el número de bordes (una ventaja sobre la búsqueda en profundidad ) ^[14]
• (Reverso) Numeración de mallas Cuthill-McKee
• Método Ford-Fulkerson para calcular el flujo máximo en una red de flujo
• La serialización/deserialización de un árbol binario versus 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 de Aho-Corasick .
• Prueba de bipartición de un gráfico .
• Implementación de algoritmos paralelos para calcular el cierre transitivo de un gráfico. ^[15]

Ver también

• Búsqueda en profundidad
• Búsqueda iterativa de profundización en profundidad
• Estructura de niveles
• Búsqueda lexicográfica primero en amplitud
• Búsqueda paralela de amplitud primero

Referencias

1. es decir, un nodo que satisface la propiedad especificada
2. Cormen Thomas H.; et al. (2009). "22,3". Introducción a los algoritmos . Prensa del MIT.
3. Korf, Richard E. (1985). "Profundización iterativa en profundidad: una búsqueda de árbol óptima admisible". Inteligencia artificial (27): 99–100. doi :10.7916/D8HQ46X1.
4. "Especificación de referencia Graph500 (evaluación del rendimiento de la supercomputadora)". Graph500.org, 2010. Archivado desde el original el 26 de marzo de 2015 . Consultado el 15 de marzo de 2015 .
5. Zuse, Konrad (1972), Der Plankalkül (en alemán), Konrad Zuse Internet Archive. Véanse las páginas 96 a 105 del archivo pdf vinculado (numeración interna 2.47 a 2.56).
6. Moore, Edward F. (1959). "El camino más corto a través de un laberinto". Actas del Simposio internacional sobre la teoría del cambio . Prensa de la Universidad de Harvard. págs. 285–292.Citado por Cormen, Leiserson, Rivest y Stein.
7. Skiena, Steven (2008). "Clasificación y búsqueda". El manual de diseño de algoritmos . Saltador. pag. 480. Bibcode : 2008adm..libro.....S. doi :10.1007/978-1-84800-070-4_4. ISBN 978-1-84800-069-8.
8. Lee, CY (1961). "Un algoritmo para conexiones de rutas y sus aplicaciones". Transacciones IRE en computadoras electrónicas (3): 346–365. doi :10.1109/TEC.1961.5219222. S2CID  40700386.
9. Cormen, Thomas H. "22.2 Búsqueda en amplitud". Introducción a los algoritmos. ISBN 978-81-203-4007-7. OCLC  1006880283.
10. "Recorrido de gráficos basado en pila ≠ primera búsqueda en profundidad". 11011110.github.io . Consultado el 10 de junio de 2020 .
11. Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001) [1990]. "22.2 Búsqueda en amplitud". Introducción a los algoritmos (2ª ed.). MIT Press y McGraw-Hill. págs. 531–539. ISBN 0-262-03293-7.
12. Russell, Estuardo ; Norvig, Peter (2003) [1995]. Inteligencia artificial: un enfoque moderno (2ª ed.). Prentice Hall. ISBN 978-0137903955.
13. Coppin, B. (2004). Inteligencia artificial iluminada. Aprendizaje de Jones y Bartlett. págs. 79–80.
14. Aziz, Adnán; Prakash, Amit (2010). "4. Algoritmos sobre gráficos". Algoritmos para Entrevistas . pag. 144.ISBN​ 978-1453792995.
15. 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, volumen 1. 3.ª ed., Boston: Addison-Wesley, ISBN 978-0-201-89683-1, archivado desde el original el 4 de septiembre de 2008 , consultado el 9 de febrero de 2008

enlaces externos

• Estructuras de datos abiertas - Sección 12.3.1 - Búsqueda en amplitud, Pat Morin