Primera búsqueda en amplitud

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 26 de abril de 2021; las comprobaciones requieren 3 ediciones .

La búsqueda primero en anchura ( BFS ) es uno de los métodos transversales de grafos .  Sea dada la gráfica y el vértice inicial . El algoritmo de búsqueda primero en amplitud atraviesa sistemáticamente todos los bordes para "descubrir" todos los vértices alcanzables desde , mientras calcula la distancia (número mínimo de bordes) desde cada vértice alcanzable . El algoritmo funciona tanto para gráficos dirigidos como no dirigidos. [una]

La búsqueda en anchura tiene este nombre porque en el proceso de recorrido vamos en anchura, es decir, antes de empezar a buscar vértices a distancia , se recorren los vértices a distancia .

La búsqueda primero en amplitud es uno de los algoritmos de búsqueda no informados [2] .

Operación del algoritmo

La búsqueda primero en amplitud funciona recorriendo los niveles individuales del gráfico , comenzando en el nodo de origen .

Considere todos los bordes salientes del nodo . Si el siguiente nodo es el nodo de destino, la búsqueda finaliza; de lo contrario, el nodo se agrega a la cola . Después de verificar todos los bordes que salen del nodo, se toma el siguiente nodo de la cola y se repite el proceso.

Descripción informal

  1. Coloque el nodo desde el que comienza la búsqueda en la cola inicialmente vacía.
  2. Recupere un nodo del principio de la cola y márquelo como implementado.
    • Si el nodo es el nodo de destino, finalice la búsqueda con un resultado de "éxito".
    • De lo contrario, todos los sucesores del nodo que aún no se implementan y no están en la cola se agregan al final de la cola.
  3. Si la cola está vacía, todos los nodos del gráfico conectado han sido escaneados, por lo tanto, el nodo de destino es inalcanzable desde el inicial; finalice la búsqueda con el resultado "fallido".
  4. Vuelve al punto 2.

Nota: la división de vértices en desplegados y no desplegados es necesaria para un grafo arbitrario (ya que puede tener ciclos). Para un árbol , esta operación no es necesaria, ya que cada vértice se seleccionará una sola vez.

Descripción formal

A continuación se muestra el pseudocódigo del algoritmo para el caso en que solo es necesario encontrar el nodo de destino. Según la aplicación específica del algoritmo, es posible que se requiera código adicional para almacenar la información necesaria (distancia desde el nodo inicial, nodo principal, etc.)

Formulación recursiva:

BFS( nodo_inicio , nodo_objetivo ) { return BFS'({ nodo_inicio }, ∅, nodo_objetivo ); } BFS'( margen , visitado , nodo_objetivo ) { if ( margen == ∅) { // Nodo de destino no encontrado devolver falso; } if ( nodo_objetivo ∈ franja ) { return true; } return BFS'({ hijo | x ∈ franja , hijo ∈ expandir( x )} \ visitado , visitado ∪ franja , nodo_objetivo ); }

Formulación iterativa:

BFS( start_node , goal_node ) { para (todos los nodos i) visitados [ i ] = false; // inicialmente la lista de nodos visitados está vacía cola .push( start_node ); // comenzando desde el nodo de origen visitado [ start_node ] = true; while (! queue .empty() ) { // hasta que la cola esté vacía node = queue .pop(); // recupera el primer elemento de la cola if ( nodo == nodo_objetivo ) { return true; // comprobar si el nodo actual es el objetivo } foreach ( child in expand( node )) { // todos los sucesores del nodo actual, ... if (visited[ child ] == false) { // ... que aún no han sido visitados ... cola .push ( niño ); // ... añadir al final de la cola... visitado [ niño ] = verdadero; // ... y marcar como visitado } } } devolver falso; // El nodo de destino es inalcanzable }

Implementación de Pascal :

función BFS ( v : Nodo ) : Booleano ; comenzar a poner en cola ( v ) ; mientras que la cola no está vacía , comience curr := dequeue () ; si es_objetivo ( actual ) , entonces comience BFS : = verdadero ; salida ; fin ; marca ( curr ) ; para siguiente en sucesores ( actual ) haga si no está marcado ( próximo ) luego comience a poner en cola ( próximo ) ; fin ; fin ; BFS := falso ; fin ;

Propiedades

Denote el número de vértices y aristas en el gráfico como y respectivamente.

Complejidad espacial

Dado que todos los nodos expandidos se almacenan en la memoria, la complejidad espacial del algoritmo es [2] .

El algoritmo de búsqueda de profundización iterativa es similar a la búsqueda en amplitud en el sentido de que cada iteración examina el nivel completo de nuevos nodos antes de pasar al siguiente nivel, pero requiere una memoria significativamente menor.

Complejidad del tiempo

Dado que en el peor de los casos el algoritmo visita todos los nodos del grafo, al almacenar el grafo en forma de listas de adyacencia , la complejidad temporal del algoritmo es [2] [3] .

Integridad

Si cada nodo tiene un número finito de sucesores, el algoritmo está completo: si existe una solución, el algoritmo de búsqueda en amplitud la encuentra, sea o no finito el gráfico. Sin embargo, si no hay solución, la búsqueda no termina en el gráfico infinito.

Optimalidad

Si las longitudes de los bordes del gráfico son iguales, la búsqueda primero en anchura es óptima, es decir, siempre encuentra la ruta más corta. En el caso de un gráfico ponderado , la búsqueda primero en anchura encuentra una ruta que contiene el número mínimo de aristas, pero no necesariamente la más corta.

La búsqueda primero en costo es una generalización de la búsqueda primero en amplitud y es óptima en un gráfico ponderado con ponderaciones de borde no negativas. El algoritmo visita los nodos del grafo en orden creciente del costo de la ruta desde el nodo de inicio y, por lo general, utiliza una cola de prioridad .

Historia y aplicaciones

La búsqueda primero en amplitud fue formalmente propuesta por E. F. Moore en el contexto de encontrar un camino en un laberinto [4] . Lee descubrió de forma independiente el mismo algoritmo en el contexto del cableado de PCB [5] [6] [7] .

La búsqueda primero en amplitud se puede aplicar a problemas relacionados con la teoría de grafos :

Véase también

Notas

  1. ↑ Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algoritmos: construcción y análisis. - 3ra ed. - Editorial Williams, 2013. - S. 630. - 1328 p. - ISBN 978-5-8459-1794-2 (ruso). - ISBN 978-0-2620-3384-8 (inglés).
  2. ↑ 1 2 3 4 5 6 MAXimal :: algo :: Primera búsqueda en amplitud en un gráfico y sus aplicaciones Archivado el 16 de septiembre de 2013 en Wayback Machine .
  3. ↑ 1 2 NSTU Estructuras y algoritmos de procesamiento de datos Recorrido de gráfico de amplitud Copia de archivo fechada el 30 de diciembre de 2012 en Wayback Machine
  4. ↑ 1 2 Moore E. F. El camino más corto a través de un laberinto  // Actas de un Simposio Internacional sobre la Teoría de la Conmutación (Cambridge, Massachusetts, 2–5 de abril de 1957) - Harvard University Press , 1959. - vol. 2.- Pág. 285-292. — 345 págs. - ( Anales del Laboratorio de Computación de la Universidad de Harvard ; Vol. 30) - ISSN 0073-0750
  5. ↑ 1 2 C. Y. Lee (1961), Un algoritmo para la conexión de rutas y sus aplicaciones . IRE Transactions on Electronic Computers , EC-10(3), págs. 346–365
  6. ↑ Cormen et al , Introducción a los algoritmos, 3.ª edición, p. 623
  7. ↑ Matemáticas Stack Exchange Origen del algoritmo de búsqueda en anchura

Literatura

  • TH Cormen, CE Leiserson, RL Rivest, C. Stein. Introducción a los Algoritmos. — 3ra edición. - MIT Press, 2009. - ISBN 978-0-262-03384-8 . . Traducción de la segunda edición: Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algoritmos: construcción y análisis = Introducción a los Algoritmos. - 2ª ed. - M .: "Williams" , 2006. - S. 1296. - ISBN 0-07-013151-1 .
  • Levitin A. V. Capítulo 5. Método de reducción del tamaño del problema: Búsqueda en amplitud // Algoritmos. Introducción al desarrollo y análisis - M. : Williams , 2006. - 576 p. — ISBN 978-5-8459-0987-9

Enlaces

 Algoritmos de búsqueda de gráficos
Métodos no informados
Métodos informados
Atajos
Árbol de expansión mínimo
Otro