Búsqueda en amplitud

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 del siguiente nivel de profundidad. Se necesita memoria adicional, normalmente 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 usar una búsqueda en amplitud 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 tener un tamaño infinito; se garantiza que la búsqueda en amplitud encontrará un nodo de solución ^[1] si existe uno.

Por el contrario, la búsqueda en profundidad (simple) (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 en profundidad con profundización iterativa evita este último inconveniente al precio de explorar las partes superiores del árbol una y otra vez. 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 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 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 conectados 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 luego desarrollado por CY Lee en un algoritmo de enrutamiento de cables (publicado en 1961). ^[8]

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 como se exploró
 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               devuelve  v 
 9           para todos los bordes desde v hasta w  en  G .adjacentEdges( v ) hace 
10               si  w no está etiquetado como explorado, entonces 
11 etiqueta w como explorado
12                   w .parent := v 
13                   Q .enqueue( w )

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 se ha explorado un vértice antes de ponerlo en cola en lugar de retrasar esta comprobación hasta que el vértice se saque de la cola.

Si G es un árbol , reemplazar la cola de este algoritmo de búsqueda en amplitud por una pila producirá un algoritmo de búsqueda en profundidad. Para los grafos generales, reemplazar la pila de la implementación iterativa de búsqueda en profundidad por una cola también produciría un algoritmo de búsqueda en amplitud, aunque uno un tanto 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 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 de inicio, una vez que se ha ejecutado el BFS y se han configurado los nodos predecesores.

La búsqueda en amplitud produce un árbol en amplitud . En el siguiente ejemplo, puede ver cómo se ve un árbol en amplitud .

El siguiente es un ejemplo del árbol en amplitud obtenido al ejecutar un BFS en ciudades alemanas comenzando desde Frankfurt :

La complejidad temporal 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 en el gráfico. Tenga en cuenta que puede variar entre y , dependiendo de qué tan disperso sea el gráfico de entrada. ^[11]${\displaystyle O(|V|+|E|)}$${\estilo de visualización |V|}$${\estilo de visualización |E|}$${\displaystyle O(|E|)}$${\estilo de visualización O(1)}$${\displaystyle O(|V|^{2})}$

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

Cuando se trabaja con gráficos que son demasiado grandes para almacenarse explícitamente (o infinitos), es más práctico describir la complejidad de la búsqueda en amplitud en términos diferentes: para encontrar los nodos que están a una distancia d del nodo de inicio (medida en número de recorridos de aristas), 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}

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 describe como completo si se garantiza que encontrará un estado objetivo si existe uno. La búsqueda en amplitud es completa, pero la búsqueda en profundidad no lo es. Cuando se aplica a gráficos infinitos representados implícitamente, la búsqueda en amplitud finalmente encontrará el estado objetivo, pero la búsqueda en profundidad puede perderse en partes del gráfico que no tienen estado objetivo y nunca regresar. ^[13]

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

Sea un grafo con vértices. Recordemos que es el conjunto de vecinos de . Sea una lista de elementos distintos de , para , sea el menor tal que sea vecino de , si existe tal , y sea en caso contrario. ${\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 origen ) si, para todo , es el vértice tal que es mínimo. De manera equivalente, es un ordenamiento BFS si, para todo 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}$

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

• Copia de la recolección de basura , 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 aristas (una ventaja sobre la búsqueda en profundidad ) ^[14]
• (Reverso) Numeración de malla Cuthill–McKee
• Método de Ford-Fulkerson para calcular el caudal 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 fallo del comparador de patrones Aho-Corasick .
• Prueba de bipartidismo de un gráfico .
• Implementación de algoritmos paralelos para calcular el cierre transitivo de un gráfico. ^[15]

• Búsqueda en profundidad
• Búsqueda iterativa de profundidad progresiva
• Estructura de niveles
• Búsqueda lexicográfica en amplitud
• Búsqueda en amplitud paralela

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