Hispanopedia Wiki
Articulo de referencia

Búsqueda en amplitud

O(|V| + |E|) "},"space":{"wt":" O(|V|) "},"optimal":{"wt":"Yes (always finds shortest paths)"}},"i":0}}]}"> BFS en el algoritmo de resolución de laberintos Parte superior del ár...

Hispanopedia WikiContenido en espanolLectura gratuita
BFS en el algoritmo de resolución de laberintos
Parte superior del árbol del juego Tres en raya

En informática , la búsqueda en anchura ( BFS , por sus siglas en inglés) es un algoritmo para buscar en una estructura de datos de árbol un nodo que cumpla 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 mantener un registro de los nodos hijos encontrados pero aún no explorados.

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 usar una búsqueda en anchura para encontrar una posición ganadora para las blancas. Los árboles implícitos (como los árboles de juego u otros árboles de resolución de problemas) pueden ser de tamaño infinito; la búsqueda en anchura garantiza encontrar un nodo de solución [ 1 ] si existe.

En contraste, la búsqueda en profundidad (DFS) simple , que explora la rama del nodo hasta donde sea posible antes de retroceder y expandir otros nodos, [ 2 ] puede perderse en una rama infinita y nunca llegar al nodo solución. La búsqueda en profundidad iterativa evita este último inconveniente a costa de explorar repetidamente las partes superiores del árbol. Por otro lado, ambos algoritmos de búsqueda en profundidad suelen requerir mucha menos memoria adicional que la búsqueda en amplitud. [ 3 ]

La búsqueda en amplitud se puede generalizar tanto a grafos no dirigidos como a grafos dirigidos con un nodo inicial dado (a veces denominado "clave de búsqueda"). [ 4 ] En la búsqueda en el 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, normalmente se toman precauciones para evitar repeticiones.

BFS y su aplicación para encontrar componentes conexas de grafos fueron inventados en 1945 por Konrad Zuse , en su tesis doctoral (rechazada) sobre el lenguaje de programación Plankalkül , pero esta 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

El siguiente pseudocódigo encuentra el camino más corto desde un vértice raíz dado a todos los demás vértices del grafo utilizando la búsqueda en amplitud (BFS).

Entrada : Un grafo G y un vértice inicial raíz de G.

Salida : Estado del objetivo. Los enlaces padre trazan el camino más corto de regreso a la raíz [ 9 ].

1 procedimiento BFS( G , raíz ) es 2 sea Q una cola 3 etiquetas raíz como se explora 4 Q .enqueue( raíz ) 5 mientras Q no esté vacío hacer 6 v := Q .dequeue() 7 si v es el objetivo entonces 8 devolver v 9 para todas las aristas de v a w en G .adjacentEdges( v ) hacer 10 si w no está etiquetado como explorado entonces 11 etiquetar w como explorado 12 w .parent := v 13 Q .enqueue( w )

Más detalles

Un ejemplo de mapa del sur de Alemania con algunas conexiones entre ciudades.
El árbol de búsqueda en anchura obtenido al ejecutar BFS en el mapa dado y comenzar en Frankfurt

Esta implementación no recursiva es similar a la implementación no recursiva de la búsqueda en profundidad , pero difiere de ella en dos aspectos:

  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 agregarlo a la cola, en lugar de retrasar esta comprobación hasta que el vértice se extraiga de la cola.

Si G es un árbol , reemplazar la cola de este algoritmo de búsqueda en anchura con una pila dará como resultado un algoritmo de búsqueda en profundidad. Para grafos 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 anchura, aunque algo atípico. [ 10 ]

La cola Q contiene la frontera a lo largo de la cual el algoritmo está buscando actualmente.

Los nodos pueden etiquetarse como explorados almacenándolos en un conjunto o mediante un atributo en cada nodo, según la implementación.

El atributo padre de cada nodo es útil para acceder a los nodos por la ruta más corta, por ejemplo, retrocediendo desde el nodo de destino hasta el nodo de inicio, una vez que se ha ejecutado la búsqueda en amplitud (BFS) y se han establecido los nodos predecesores.

La búsqueda en anchura produce un árbol en anchura . Los diagramas de la derecha muestran el árbol en anchura obtenido al ejecutar una búsqueda en anchura en un grafo de ejemplo de ciudades alemanas (diagrama superior) comenzando desde Frankfurt .

Análisis

Complejidad temporal y espacial

La complejidad temporal se puede expresar comoO(|V|+|mi|){\displaystyle O(|V|+|E|)}, ya que en el peor de los casos se explorarán todos los vértices y todas las aristas.|V|{\displaystyle |V|}es el número de vértices y|mi|{\displaystyle |E|}es el número de aristas en el grafo. Tenga en cuenta queO(|mi|){\displaystyle O(|E|)}puede variar entreO(1){\displaystyle O(1)}yO(|V|2){\displaystyle O(|V|^{2})}, dependiendo de cuán disperso sea el grafo de entrada. [ 11 ]

Cuando se conoce de antemano el número de vértices del grafo y se utilizan estructuras de datos adicionales para determinar qué vértices ya se han añadido a la cola, la complejidad espacial se puede expresar comoO(|V|){\displaystyle O(|V|)}, dónde|V|{\displaystyle |V|}es el número de vértices. Esto se suma al espacio requerido para el grafo en sí, que puede variar según la representación gráfica utilizada por la implementación del algoritmo.

Cuando se trabaja con grafos demasiado grandes para almacenarlos explícitamente (o infinitos), resulta más práctico describir la complejidad de la búsqueda en anchura en términos diferentes: para encontrar los nodos que se encuentran a una distancia d del nodo inicial (medida en número de recorridos de aristas), la búsqueda en anchura requiere un tiempo y una memoria de O ( b d + 1 ) , donde b es el " factor de ramificación " del grafo (el grado de salida promedio). [ 12 ] : 81

Lo completo

En el análisis de algoritmos, se asume que la entrada para la búsqueda en amplitud es un grafo 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 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 garantiza encontrar un estado objetivo si existe. La búsqueda en amplitud es completa, pero la búsqueda en profundidad no lo es. Cuando se aplica a grafos 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 grafo que no tienen un estado objetivo y nunca regresar. [ 13 ]

Pedidos BFS

Se dice que una enumeración de los vértices de un grafo es un ordenamiento BFS si es un resultado posible de la aplicación de BFS a dicho grafo.

DejarGRAMO=(V,mi){\displaystyle G=(V,E)}ser un gráfico connorte{\displaystyle n}vértices. Recuerda quenorte(v){\displaystyle N(v)}es el conjunto de vecinos dev{\displaystyle v}. Dejarσ=(v1,…,vmetro){\displaystyle \sigma =(v_{1},\dots,v_{m})}ser una lista de elementos distintos deV{\displaystyle V}, parav∈V∖{v1,…,vmetro}{\displaystyle v\in V\setminus \{v_{1},\dots,v_{m}\}}, dejarνσ(v){\displaystyle \nu _ {\sigma }(v)}ser el menosi{\displaystyle i}de tal manera quevi{\displaystyle v_{i}}es vecino dev{\displaystyle v}, si tal es uni{\displaystyle i}existe y ser∞{\displaystyle \infty }de lo contrario.

Dejarσ=(v1,…,vnorte){\displaystyle \sigma =(v_{1},\dots,v_{n})}ser una enumeración de los vértices deV{\displaystyle V}. La enumeraciónσ{\displaystyle \sigma }Se dice que es un ordenamiento BFS (con fuente)v1{\displaystyle v_{1}}) si, para todos1<i≤norte{\displaystyle 1<i\leq n},vi{\displaystyle v_{i}}es el vérticew∈V∖{v1,…,vi−1}{\displaystyle w\in V\setminus \{v_{1},\dots,v_{i-1}\}}de tal manera queν(v1,…,vi−1)(w){\displaystyle \nu _ {(v_{1},\dots,v_{i-1})}(w)}es mínimo. Equivalentemente,σ{\displaystyle \sigma }es un ordenamiento BFS si, para todos1≤i<j<k≤norte{\displaystyle 1\leq i<j<k\leq n}convi∈norte(vk)∖norte(vj){\ Displaystyle v_ {i} \ en N (v_ {k}) \ setminus N (v_ {j})}, existe un vecino vmetro{\displaystyle v_{m}}devj{\displaystyle v_{j}}de tal manera quemetro<i{\displaystyle m<i}.

Aplicaciones

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

Véase también

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 . MIT Press.
  3. ↑ Korf, Richard E. (1985). "Depth-First Iterative Deepening: An Optimal Admissible Tree Search" . Artificial Intelligence (27): 99–100 . doi : 10.7916/D8HQ46X1 .
  4. ↑ "Especificación de referencia Graph500 (evaluación del rendimiento de supercomputadoras)" . Graph500.org, 2010. Archivado del 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 ArchiveConsulte las páginas 96 a 105 del archivo PDF adjunto (numeración interna 2.47–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 de la Conmutación . Harvard University Press. págs. 285–292 . Según lo citado por Cormen, Leiserson, Rivest y Stein.
  7. ↑ Skiena, Steven (2008). "Clasificación y búsqueda". Manual de diseño de algoritmos . Springer. pág. 480. Bibcode : 2008adm..book.....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". IRE Transactions on Electronic Computers (3): 346– 365. doi : 10.1109/TEC.1961.5219222 . S2CID 40700386 . 
  9. ↑ Cormen, Thomas H. (enero de 2010). "22.2 Búsqueda en amplitud". Introducción a los algoritmos . Prentice-Hall Of India Pvt. Limited. ISBN 978-81-203-4007-7OCLC 1006880283​​ 
  10. ↑ "Recorrido de grafos basado en pilas ≠ 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, Stuart ; Norvig, Peter (2003) [1995]. Inteligencia artificial: un enfoque moderno (2.ª ed.). Prentice Hall. ISBN  978-0137903955.
  13. ↑ Coppin, B. (2004). Inteligencia artificial iluminada. Jones & Bartlett Learning. pp. 79–80.
  14. ↑ Aziz, Adnan; Prakash, Amit (2010). "4. Algoritmos en grafos". Algorithms for Interviews . Algorithmsforinterviews.com. pág. 144. ISBN  978-1453792995.
  15. ↑ Kleinberg, Jon ; Tardos, Éva (2006), Diseño de algoritmos , Addison Wesley, págs . 94-97 .
  16. ↑ Dhulipala, Laxman; Blelloch, Guy E.; Shun, Julian (21 de agosto de 2019). Los algoritmos de grafos paralelos teóricamente eficientes pueden ser rápidos y escalables . pág. 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-1Archivado del original el 4 de septiembre de 2008 , consultado el 9 de febrero de 2008.
  • Estructuras de datos abiertas - Sección 12.3.1 - Búsqueda en amplitud , Pat Morin