Búsqueda primero en amplitud - Breadth-first search

Búsqueda en amplitud primero

Orden en el que se expanden los nodos
Clase	Algoritmo de búsqueda
Estructura de datos	Grafico
Rendimiento en el peor de los casos	${\ Displaystyle O (| V | + | E |) = O (b ^ {d})}$
Complejidad espacial en el peor de los casos	${\ Displaystyle O (| V |) = O (b ^ {d})}$

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

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

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

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 la búsqueda de amplitud para encontrar un nodo de solución, si existe.

Por el contrario, la búsqueda en profundidad (simple) , que explora la rama del nodo en la medida de lo posible antes de retroceder y expandir otros nodos, 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") se proporciona explícitamente y se toman precauciones para no seguir 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. Fue reinventado en 1959 por Edward F. Moore , quien lo usó para encontrar el camino más corto para salir de un laberinto, y luego desarrollado por CY Lee en un algoritmo de enrutamiento de cables (publicado en 1961).

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.

 1  procedure BFS(G, root) is
 2      let Q be a queue
 3      label root as explored
 4      Q.enqueue(root)
 5      while Q is not empty do
 6          v := Q.dequeue()
 7          if v is the goal then
 8              return v
 9          for all edges from v to w in G.adjacentEdges(v) do
10              if w is not labeled as explored then
11                  label w as explored
12                  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:

1. utiliza una cola (primero en entrar, primero en salir) en lugar de una pila y
2. 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.

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 :

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 borde se explorarán en el peor de los casos. es el número de vértices y es el número de aristas en el gráfico. Tenga en cuenta que puede variar entre y , dependiendo de cuán escaso sea el gráfico de entrada. ${\ Displaystyle O (| V | + | E |)}$${\ Displaystyle | V |}$${\ Displaystyle | E |}$${\ Displaystyle O (| E |)}$${\ Displaystyle O (1)}$${\ Displaystyle O (| V | ^ {2})}$

Cuando se conoce el número de vértices en el gráfico de antemano 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. ${\ 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: 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).

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.

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.

Sea una gráfica con vértices. Recordemos que es el conjunto de vecinos de . Sea una lista de elementos distintos de , pues , sea ​​el menor tal que sea ​​vecino de , si tal existe, y sea de otro modo. ${\ 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 . La enumeración se dice que es un ordenamiento BFS (con fuente ) si, para todos , es el vértice de tal forma que es mínima. De manera equivalente, es un ordenamiento BFS si, para todos con , existe un vecino de 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 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 )
• (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.

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

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