Búsqueda en amplitud

Ejemplo animado de una búsqueda de amplitud. Negro: explorado, gris: queued to be explored later on

BFS en algoritmo de resolución de laberinto

Parte superior de Tic-tac-toe juego árbol

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 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 los árboles de juego u otros árboles de resolución de problemas) pueden tener un tamaño infinito; Se garantiza que la búsqueda primero en amplitud encuentre un nodo de solución, si existe.

Por el contrario, la búsqueda en profundidad (simple), que explora la rama del nodo tanto como sea 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 primero en profundidad iterativa evita este último inconveniente al precio de explorar las partes superiores del árbol una y otra vez. Por otro lado, ambos algoritmos de profundidad primero se llevan bien sin memoria adicional.

La búsqueda primero en amplitud 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 grafos 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 un vértice inicial raíz de G

Salida: estado del objetivo. Los enlaces principales rastrean la ruta más corta de regreso a raíz

 1 procedimiento BFS(G, root) es2 Q ser una cola
3 etiquetas root como explorado
4 Q.enqueue(root)
5 mientras Q no está vacío do6 v:= Q.dequeue()
7 si v es el objetivo entonces8 retorno v9 para todos bordes de v a w dentro G.adjacentEdges(v) do10 si w no está etiquetado como explorado entonces11 etiquetas w como explorado
12 w.parent:= v13 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 en dos formas:

1. usa una cola (Primero en Primera salida) en lugar de una pila y
2. comprueba si se ha explorado un vértice antes de encubrir el vértice en lugar de retrasar este cheque hasta que el vértice se desprenda de la cola.

Si G es un árbol, reemplazar la cola de este algoritmo de búsqueda en anchura con una pila generará una profundidad- primer algoritmo de búsqueda. Para gráficos generales, reemplazar la pila de la implementación iterativa de búsqueda primero en profundidad con una cola también produciría un algoritmo de búsqueda primero 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 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 de inicio, una vez que se haya ejecutado el BFS y el se han establecido los nodos predecesores.

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

Ejemplo

El siguiente es un ejemplo del árbol primero en anchura obtenido al ejecutar un BFS en ciudades alemanas a partir de Fráncfort:

Un ejemplo de mapa de Alemania del Sur con algunas conexiones entre ciudades

El primer árbol obtenido al correr BFS en el mapa dado y empezar en Frankfurt

Análisis

Complejidad de tiempo y espacio

La complejidad del tiempo se puede expresar como O()SilencioVSilencio+SilencioESilencio){displaystyle O(vivienda), ya que cada vértice y cada borde serán explorados en el peor caso. SilencioVSilencio{displaystyle Silencioso es el número de vértices y SilencioESilencio{displaystyle Silencioso es el número de bordes en el gráfico. Note que O()SilencioESilencio){displaystyle O(viviendas)} puede variar entre O()1){displaystyle O(1)} y O()SilencioVSilencio2){displaystyle O {fnMicrosoft Sans Serif}, dependiendo de cómo es escasa el gráfico de entrada.

Cuando el número de vértices en el gráfico se conoce por adelantado, 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 como O()SilencioVSilencio){displaystyle O(vivienda)}, donde SilencioVSilencio{displaystyle Silencioso es el número de vértices. Esto es además del espacio requerido para el propio gráfico, que puede variar dependiendo de la representación gráfica utilizada por la implementación del algoritmo.

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 distancia d desde el nodo de inicio (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).

Integridad

En el análisis de algoritmos, se supone que la entrada para la búsqueda en anchura 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. La búsqueda primero en amplitud está completa, pero la búsqueda primero en profundidad no lo está. Cuando se aplica a gráficos infinitos representados implícitamente, la búsqueda primero en amplitud finalmente encontrará el estado objetivo, pero la búsqueda primero en profundidad puede perderse en partes del gráfico que no tienen 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 posible resultado de la aplicación de BFS a este gráfico.

Vamos G=()V,E){displaystyle G=(V,E)} ser un gráfico con n{displaystyle n} vertices. Recordad que N()v){displaystyle N(v)} es el conjunto de vecinos de v{displaystyle v}. Vamos σ σ =()v1,...... ,vm){displaystyle sigma =(v_{1},dotsv_{m}} ser una lista de elementos distintos V{displaystyle V}, para v▪ ▪ V∖ ∖ {}v1,...... ,vm}{displaystyle vin Vsetminus {v_{1},dotsv_{m}}, vamos .. σ σ ()v){displaystyle nu _{sigma }(v)} ser el menos i{displaystyle i} tales que vi{displaystyle V_{i} es un vecino v{displaystyle v}, si tal i{displaystyle i} existe, y ser JUEGO JUEGO {displaystyle infty } De lo contrario.

Vamos σ σ =()v1,...... ,vn){displaystyle sigma =(v_{1},dotsv_{n}} ser una enumeración de los vértices V{displaystyle V}. La enumeración σ σ {displaystyle sigma } se dice que es una orden BFS (con fuente) v1{displaystyle v_{1}Si, para todos <math alttext="{displaystyle 11.i≤ ≤ n{displaystyle 1 0}<img alt="{displaystyle 1, vi{displaystyle V_{i} es el vértice w▪ ▪ V∖ ∖ {}v1,...... ,vi− − 1}{displaystyle win Vsetminus {v_{1},dotsv_{i-1}} tales que .. ()v1,...... ,vi− − 1)()w){displaystyle nu _{(v_{1},dotsv_{i-1}(w)} es mínimo. Equivalentemente, σ σ {displaystyle sigma } es un BFS ordenando si, para todos <math alttext="{displaystyle 1leq i<j1≤ ≤ i.j.k≤ ≤ n{displaystyle 1leq i obedeciókleq n}<img alt="{displaystyle 1leq i<j con vi▪ ▪ N()vk)∖ ∖ N()vj){displaystyle v_{i}in N(v_{k})setminus N(v_{j}}, existe un vecino vm{displaystyle V_{m} de vj{displaystyle v_{j} tales que <math alttext="{displaystyle mm.i{displaystyle m woni}<img alt="{displaystyle m.

Aplicaciones

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

• Copiando la colección de basura, algoritmo de Cheney
• Encontrar el camino más corto entre dos nodos u y v, con longitud de la ruta medida por el número de bordes (una ventaja sobre la búsqueda de profundidad)
• (Reverso) Cuthill–McKee mesh numbering
• Ford-Fulkerson método para calcular el flujo máximo en una red de flujo
• Serialización/Deserialización de un árbol binario vs serialization en orden ordenado, permite que el árbol sea re-construido de una manera eficiente.
• Construcción de la función de fallo del matcher de patrón Aho-Corasick.
• Probando bipartidismo de un gráfico.
• Implementando algoritmos paralelos para calcular el cierre transitivo de un gráfico.