LISTAS RELACIONADAS CON LAS MATEMÁTICAS - ALGORITMOS

La búsqueda bidireccional es un algoritmo de búsqueda de gráficos que encuentra una ruta más corta desde un vértice inicial hasta un vértice objetivo en un gráfico dirigido . Ejecuta dos búsquedas simultáneas: una hacia adelante desde el estado inicial y otra hacia atrás desde la meta, deteniéndose cuando los dos se encuentran. La razón de este enfoque es que en muchos casos es más rápido: por ejemplo, en un modelo simplificado de complejidad del problema de búsqueda en el que ambas búsquedas expanden un árbol con el factor de ramificación b , y la distancia desde el inicio hasta el objetivo es d , cada uno de los dos búsquedas tiene complejidad O ( b ^{d / 2} ) (enNotación O grande ), y la suma de estos dos tiempos de búsqueda es mucho menor que la complejidad O ( b ^d ) que resultaría de una sola búsqueda desde el principio hasta el objetivo.

Andrew Goldberg y otros explicaron las condiciones correctas de terminación para la versión bidireccional del algoritmo de Dijkstra . ^[1]

Al igual que en la búsqueda A * , la búsqueda bidireccional puede guiarse por una estimación heurística de la distancia restante a la meta (en el árbol hacia adelante) o desde el principio (en el árbol hacia atrás).

Ira Pohl ( 1971 ) fue el primero en diseñar e implementar un algoritmo de búsqueda heurística bidireccional. Los árboles de búsqueda que emanan desde el inicio y los nodos de objetivos no se encontraron en el medio del espacio de la solución. El algoritmo BHFFA solucionó este defecto Champeaux (1977).

Una solución encontrada por el algoritmo unidireccional A * que utiliza una heurística admisible tiene una longitud de ruta más corta; la misma propiedad es válida para la versión heurística bidireccional BHFFA2 descrita en de Champeaux (1983). BHFFA2 tiene, entre otras, condiciones de terminación más cuidadosas que BHFFA.

Descripción [ editar ]

Una búsqueda heurística bidireccional es una búsqueda de espacio de estado de algún estado$${\ displaystyle s} a otro estado $${\ displaystyle t}, buscando desde $${\ displaystyle s} a $${\ displaystyle t} y de $${\ displaystyle t} a $${\ displaystyle s}simultaneamente. Devuelve una lista válida de operadores que, si se aplican a$${\ displaystyle s} nos dará $${\ displaystyle t}.

Si bien puede parecer que los operadores tienen que ser invertibles para la búsqueda inversa, solo es necesario poder encontrar, dado cualquier nodo $${\ displaystyle n}, el conjunto de nodos principales de $${\ displaystyle n} tal que existe algún operador válido de cada uno de los nodos principales para $${\ displaystyle n}. Esto a menudo se ha comparado con una calle de sentido único en el dominio de búsqueda de ruta: no es necesario poder descender en ambas direcciones, pero es necesario cuando se está parado al final de la calle para determinar el comienzo de la calle. como una posible ruta

De manera similar, para aquellos bordes que tienen arcos inversos (es decir, arcos que van en ambas direcciones) no es necesario que cada dirección tenga el mismo costo. La búsqueda inversa siempre utilizará el costo inverso (es decir, el costo del arco en la dirección hacia adelante). Más formalmente, si$${\ displaystyle n} es un nodo con padre $${\ displaystyle p}, entonces $${\ displaystyle k_ {1} (p, n) = k_ {2} (n, p)}, definido como el costo de $${\ displaystyle p} a $${\ displaystyle n}(Auer Kaindl 2004)

Terminología y notación [ editar ]

$${\ displaystyle b} 

el factor de ramificación de un árbol de búsqueda

$${\ displaystyle k (n, m)} 

el costo asociado con mudarse del nodo $${\ displaystyle n} al nodo $${\ displaystyle m}

$${\ displaystyle g (n)} 

el costo desde la raíz hasta el nodo $${\ displaystyle n}

$${\ displaystyle h (n)} 

La estimación heurística de la distancia entre el nodo $${\ displaystyle n} y el gol

$${\ displaystyle s} 

el estado inicial

$${\ displaystyle t} 

el estado del objetivo (a veces $${\ displaystyle g}, no debe confundirse con la función)

$${\ displaystyle d} 

La dirección de búsqueda actual. Por convención,$${\ displaystyle d} es igual a 1 para la dirección hacia adelante y 2 para la dirección hacia atrás (Kwa 1989)

$${\ displaystyle d '} 

la dirección de búsqueda opuesta (es decir $${\ displaystyle d '= 3-d})

$${\ displaystyle \ mathrm {TREE} _ {d}} 

el árbol de búsqueda en dirección d. Si$${\ displaystyle d = 1}, la raíz es $${\ displaystyle s}, Si $${\ displaystyle d = 2}, la raíz es $${\ displaystyle t}

$${\ displaystyle \ mathrm {OPEN} _ {d}} 

las hojas de $${\ displaystyle \ mathrm {TREE} _ {d}} (a veces denominado $${\ displaystyle \ mathrm {FRINGE} _ {d}}) Es de este conjunto que se elige un nodo para la expansión. En la búsqueda bidireccional, a veces se les llama 'fronteras' o 'frentes de onda' de búsqueda, en referencia a cómo aparecen cuando una búsqueda se representa gráficamente. En esta metáfora, una 'colisión' ocurre cuando, durante la fase de expansión, se encuentra que un nodo de un frente de onda tiene sucesores en el frente de onda opuesto.

$${\ displaystyle \ mathrm {CERRADO} _ {d}} 

los nodos no hoja de $${\ displaystyle \ mathrm {TREE} _ {d}}. Este conjunto contiene los nodos ya visitados por la búsqueda

Enfoques para la búsqueda heurística bidireccional [ editar ]

Los algoritmos bidireccionales se pueden dividir en tres categorías: de adelante hacia adelante, de adelante hacia atrás (o de adelante hacia atrás) y la búsqueda de perímetro (Kaindl Kainz 1997). Estos difieren según la función utilizada para calcular la heurística.

De adelante hacia atrás [ editar ]

Los algoritmos de adelante hacia atrás calculan el $${\ displaystyle h} valor de un nodo $${\ displaystyle n} mediante el uso de la estimación heurística entre $${\ displaystyle n} y la raíz del árbol de búsqueda opuesto, $${\ displaystyle s} o $${\ displaystyle t}.

Front-to-Back es la más investigada de las tres categorías. El mejor algoritmo actual (al menos en el dominio de los quince rompecabezas ) es el algoritmo BiMAX-BS * F, creado por Auer y Kaindl (Auer, Kaindl 2004).

De frente a frente [ editar ]

Los algoritmos de frente a frente calculan el valor h de un nodo n utilizando la estimación heurística entre ny un subconjunto de$${\ displaystyle \ mathrm {OPEN} _ {d '}}. El ejemplo canónico es el BHFFA ( Algoritmo heurístico bidireccional de frente a frente ), ^[2] donde la función h se define como el mínimo de todas las estimaciones heurísticas entre el nodo actual y los nodos en el frente opuesto. O, formalmente:

$${\ displaystyle h_ {d} (n) = \ min _ {i} \ left \ {H (n, o_ {i}) | o_ {i} \ in \ mathrm {OPEN} _ {d '} \ right \ }}

dónde $${\ displaystyle H (n, o)}devuelve una estimación heurística admisible (es decir, no sobreestimando) de la distancia entre los nodos n y o .

Front-to-Front sufre de ser excesivamente exigente desde el punto de vista informático. Cada vez que un nodo n se coloca en la lista abierta, su$${\ displaystyle f = g + h}El valor debe ser calculado. Esto implica calcular una estimación heurística de n para cada nodo en el conjunto OPEN opuesto , como se describió anteriormente. Los conjuntos ABIERTOS aumentan de tamaño exponencialmente para todos los dominios con b > 1 .

Breadth-first search ( BFS ) es un algoritmo para atravesar o buscar estructuras de datos de árbol o gráfico . Comienza en la raíz del árbol (o algún nodo arbitrario de un gráfico, a veces denominado "clave de búsqueda" ^[1] ), y explora todos los nodos vecinos en la profundidad actual antes de pasar a los nodos en el siguiente nivel de profundidad

Utiliza la estrategia opuesta como búsqueda de profundidad primero , que explora los nodos de mayor profundidad primero antes de verse obligado a retroceder y expandir nodos menos profundos.

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 fue publicado hasta 1972. ^[2] Fue reinventado en 1959 por Edward F. Moore , quien lo utilizó para encontrar el camino más corto fuera de un laberinto, ^[3] [4] y más tarde desarrollado por CY Lee en un algoritmo de enrutamiento de cables (publicado en 1961).

Búsqueda de amplitud

Orden en el que se expanden los nodos
Clase	Algoritmo de búsqueda
Estructura de datos	Grafico
El peor de los casos	$${\ displaystyle O (| V | + | E |) = O (b ^ {d})}
La peor complejidad del espacio	$${\ displaystyle O (| V |) = O (b ^ {d})}

Pseudocódigo

Entrada : un gráfico Graph y una raíz de vértice inicial de Graph

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

1   procedimiento BFS ( G , start_v ):
2 deja que Q sea ​​una cola
3 etiqueta start_v como se descubrió
4       Q .enqueue ( start_v )
5       mientras  Q no está vacío
6           v = Q .dequeue ()
7           si  v es el objetivo:
8               devuelve  v 
9           para todos los bordes de v a w  en  G. adyacentes Bordes ( v ) do 
10              si  w no está etiquetado como descubierto:
11 etiqueta w como descubierta
12                  w .parent = v 
13                  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 difiere 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 descubierto un vértice antes de ponerlo en cola en lugar de retrasar esta comprobación hasta que el vértice se retire de la cola.

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

Los nodos se pueden etiquetar como descubiertos almacenándolos en un conjunto o mediante un atributo en cada nodo, dependiendo de la implementación.

Tenga en cuenta que la palabra nodo es generalmente 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 de amplitud produce un llamado primer árbol de amplitud . Puede ver cómo se ve un primer árbol de ancho en el siguiente ejemplo.

Ejemplo

El siguiente es un ejemplo del primer árbol de amplitud obtenido 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 primer árbol de amplitud obtenido al ejecutar BFS en el mapa dado y comenzar en Frankfurt

Análisis

Complejidad de tiempo y espacio

La complejidad del tiempo se puede expresar como $${\ displaystyle O (| V | + | E |)}, ya que cada vértice y cada borde se explorarán en el peor de los casos. $${\ displaystyle | V |} es el número de vértices y $${\ displaystyle | E |}es el número de aristas en el gráfico. Tenga en cuenta que$${\ displaystyle O (| E |)} puede variar entre $${\ displaystyle O (1)} y $${\ displaystyle O (| V | ^ {2})}, dependiendo de cuán escaso sea el gráfico de entrada. ^[6]

Cuando el número de vértices en el gráfico se conoce con anticipación, 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 $${\ displaystyle O (| V |)}, dónde $${\ displaystyle | V |}es la cardinalidad del conjunto de vértices. Esto se suma al espacio requerido para el gráfico en sí mismo, que puede variar según la representación gráfica utilizada por una implementación del algoritmo.

Cuando se trabaja con gráficos que son demasiado grandes para almacenar explícitamente (o infinito), es más práctico describir la complejidad de la búsqueda de amplitud primero en diferentes términos: para encontrar los nodos que están a la distancia d del nodo de inicio (medido en número de los 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). ^[7] : 81

Lo completo

En el análisis de algoritmos, se supone que la entrada a la búsqueda de amplitud es un gráfico finito, representado explícitamente como una lista 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 de amplitud es completa, pero la búsqueda de profundidad no lo es. Cuando se aplica a gráficos infinitos representados implícitamente, la búsqueda por amplitud finalmente encontrará el estado objetivo, pero la búsqueda por profundidad puede perderse en partes del gráfico que no tienen estado objetivo y nunca regresan. ^[8]

Pedido BFS

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

Dejar $${\ displaystyle G = (V, E)} ser un gráfico con $${\ displaystyle n}vértices Recordar que$${\ displaystyle N (v)} es el conjunto de vecinos de $${\ displaystyle v}. por$${\ displaystyle \ sigma = (v_ {1}, \ dots, v_ {m})} ser una lista de elementos distintos de $${\ displaystyle V}, para $${\ displaystyle v \ en V \ setminus \ {v_ {1}, \ dots, v_ {m} \}}, dejar $${\ displaystyle \ nu _ {\ sigma} (v)} ser el menos $${\ displaystyle i} tal que $${\ displaystyle v_ {i}} es vecino de $${\ displaystyle v}, si tal $${\ displaystyle i} existe y ser $${\ displaystyle \ infty} de otra manera.

Dejar $${\ displaystyle \ sigma = (v_ {1}, \ dots, v_ {n})} ser una enumeración de los vértices de $${\ displaystyle V}. La enumeración$${\ displaystyle \ sigma} se dice que es un pedido BFS (con fuente $${\ displaystyle v_ {1}}) si, para todos {\ displaystyle 1 , $${\ displaystyle v_ {i}} es el vértice $${\ displaystyle w \ en V \ setminus \ {v_ {1}, \ dots, v_ {i} -1 \}} tal que $${\ displaystyle \ nu _ {(v_ {1}, \ dots, v_ {i-1})} (w)}es mínimo Equivalentemente$${\ displaystyle \ sigma} es un pedido BFS si, para todos {\ displaystyle 1 \ leq i  con $${\ displaystyle v_ {i} \ en N (v_ {k}) \ setminus N (v_ {j})}existe un vecino $${\ displaystyle v_ {m}} de $${\ displaystyle v_ {j}} tal que {\ displaystyle m .

Aplicaciones

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

• Copiar 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 de profundidad primero ) ^[9]
• (Reverso) Numeración de malla Cuthill – McKee
• Método 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 que el árbol se reconstruya de manera eficiente.
• Construcción de la función de falla del emparejador de patrones Aho-Corasick .
• Prueba de bipartidismo de un gráfico .