La búsqueda de profundidad primero ( DFS ) es un algoritmo para atravesar o buscar estructuras de datos de árbol o gráfico . El algoritmo comienza en el nodo raíz (seleccionando algún nodo arbitrario como nodo raíz en el caso de un gráfico) y explora lo más posible a lo largo de cada rama antes de retroceder .
Una versión de búsqueda de profundidad fue investigada en el siglo XIX por el matemático francés Charles Pierre Trémaux [1] como una estrategia para resolver laberintos .
Orden en el que se visitan los nodos | |
Clase | Algoritmo de búsqueda |
---|---|
Estructura de datos | Grafico |
El peor de los casos | para gráficos explícitos recorridos sin repetición, para gráficos implícitos con factor de ramificación b buscado a profundidad d |
La peor complejidad del espacio | si se recorre todo el gráfico sin repetición, O (longitud de ruta más larga buscada) = para gráficos implícitos sin eliminación de nodos duplicados |
Propiedades [ editar ]
El análisis de tiempo y espacio de DFS difiere según su área de aplicación. En informática teórica, el DFS se usa típicamente para atravesar un gráfico completo y lleva tiempo, [4] lineal en el tamaño del gráfico. En estas aplicaciones también usa espacioen el peor de los casos, para almacenar la pila de vértices en la ruta de búsqueda actual, así como el conjunto de vértices ya visitados. Por lo tanto, en esta configuración, los límites de tiempo y espacio son los mismos que para la búsqueda de amplitud y la elección de cuál de estos dos algoritmos usar depende menos de su complejidad y más de las diferentes propiedades de los ordenamientos de vértices que producen los dos algoritmos. .
Para las aplicaciones de DFS en relación con dominios específicos, como la búsqueda de soluciones en inteligencia artificial o rastreo web, el gráfico que se va a recorrer es a menudo demasiado grande para visitarlo en su totalidad o infinito (DFS puede sufrir la no terminación ). En tales casos, la búsqueda solo se realiza a una profundidad limitada; Debido a los recursos limitados, como la memoria o el espacio en disco, normalmente no se utilizan estructuras de datos para realizar un seguimiento del conjunto de todos los vértices visitados anteriormente. Cuando la búsqueda se realiza a una profundidad limitada, el tiempo sigue siendo lineal en términos del número de vértices y bordes expandidos (aunque este número no es el mismo que el tamaño de todo el gráfico porque algunos vértices pueden buscarse más de una vez y otros no del todo), pero la complejidad espacial de esta variante de DFS es solo proporcional al límite de profundidad y, como resultado, es mucho menor que el espacio necesario para buscar a la misma profundidad utilizando la búsqueda de amplitud. Para tales aplicaciones, DFS también se presta mucho mejor a los métodos heurísticos para elegir una rama de aspecto probable. Cuando no se conoce un límite de profundidad apropiado a priori,La búsqueda iterativa de profundización en profundidad aplica DFS repetidamente con una secuencia de límites crecientes. En el modo de análisis de inteligencia artificial, con un factor de ramificación mayor que uno, la profundización iterativa aumenta el tiempo de ejecución solo en un factor constante sobre el caso en el que se conoce el límite de profundidad correcto debido al crecimiento geométrico del número de nodos por nivel .
DFS también se puede usar para recolectar una muestra de nodos gráficos. Sin embargo, la DFS incompleta, de manera similar a la BFS incompleta , está sesgada hacia los nodos de alto grado .
Ejemplo [ editar ]
Para el siguiente gráfico:
una búsqueda de profundidad primero que comienza en A, suponiendo que los bordes izquierdos en el gráfico que se muestran se eligen antes que los bordes derechos, y suponiendo que la búsqueda recuerda los nodos visitados anteriormente y no los repetirá (ya que este es un gráfico pequeño), visitará los nodos en el siguiente orden: A, B, D, F, E, C, G. Los bordes atravesados en esta búsqueda forman un árbol Trémaux , una estructura con importantes aplicaciones en la teoría de grafos . Realizar la misma búsqueda sin recordar los nodos visitados anteriormente resulta en nodos de visita en el orden A, B, D, F, E, A, B, D, F, E, etc. para siempre, atrapados en A, B, D, F , Ciclo E y nunca alcanzando C o G.
La profundización iterativa es una técnica para evitar este bucle infinito y llegaría a todos los nodos.
Salida de una búsqueda de profundidad primero [ editar ]
Una descripción conveniente de una búsqueda en profundidad de un gráfico es en términos de un árbol de expansión de los vértices alcanzados durante la búsqueda. Con base en este árbol de expansión, los bordes del gráfico original se pueden dividir en tres clases: bordes delanteros , que apuntan desde un nodo del árbol a uno de sus descendientes, bordes posteriores , que apuntan desde un nodo a uno de sus antepasados, y bordes transversales , que tampoco lo hacen. A veces, los bordes de los árboles , que pertenecen al árbol de expansión en sí, se clasifican por separado de los bordes delanteros. Si el gráfico original no está dirigido, todos sus bordes son bordes de árbol o bordes posteriores.
Pedidos DFS [ editar ]
Se dice que una enumeración de los vértices de un gráfico es un pedido DFS si es el posible resultado de la aplicación de DFS a este gráfico.
Dejar ser un gráfico con vértices por ser una lista de elementos distintos de , para , dejar ser el mejor tal que es vecino de , si tal existe y ser de otra manera.
Dejar ser una enumeración de los vértices de . La enumeración se dice que es un pedido DFS (con fuente ) si, para todos , es el vértice tal que es máximo Recordar que es el conjunto de vecinos de . Equivalentemente es un pedido DFS si, para todos con existe un vecino de tal que .
Pedidos de vértices [ editar ]
También es posible usar la búsqueda de profundidad primero para ordenar linealmente los vértices de un gráfico o árbol. Hay tres formas comunes de hacer esto:
- Un pedido anticipado es una lista de los vértices en el orden en que fueron visitados por primera vez por el algoritmo de búsqueda de profundidad primero. Esta es una forma compacta y natural de describir el progreso de la búsqueda, como se hizo anteriormente en este artículo. Un pedido previo de un árbol de expresión es la expresión en notación polaca .
- Un postorder es una lista de los vértices en el orden en que fueron visitados por última vez por el algoritmo. Una posposición de un árbol de expresión es la expresión en notación polaca inversa .
- Un postorder inverso es el reverso de un postordering, es decir, una lista de los vértices en el orden opuesto de su última visita. El postorder inverso no es lo mismo que el preorden.
Por ejemplo, al buscar el gráfico dirigido a continuación que comienza en el nodo A, la secuencia de recorridos es ABDBACA o ACDCABA (la elección de visitar primero B o C desde A depende del algoritmo). Tenga en cuenta que las visitas repetidas en forma de retroceso a un nodo, para verificar si todavía tiene vecinos no visitados, se incluyen aquí (incluso si se descubre que no tiene ninguno). Por lo tanto, los posibles pedidos anticipados son ABDC y ACDB, mientras que los posibles anuncios son DBCA y DCBA, y los posibles pedidos inversos son ACBD y ABC D.
La publicación inversa produce una clasificación topológica de cualquier gráfico acíclico dirigido . Este orden también es útil en el análisis de flujo de control, ya que a menudo representa una linealización natural de los flujos de control. El gráfico anterior puede representar el flujo de control en el fragmento de código a continuación, y es natural considerar este código en el orden ABCD o ACBD, pero no es natural usar el orden ABDC o ACD B.
Pseudocódigo [ editar ]
Entrada : un gráfico G y un vértice v de G
Salida : todos los vértices accesibles desde v etiquetados como descubiertos
Una implementación recursiva de DFS: [5]
Estas dos variaciones de DFS visitan a los vecinos de cada vértice en orden opuesto: el primer vecino de v visitado por la variación recursiva es el primero en la lista de bordes adyacentes, mientras que en la variación iterativa el primer vecino visitado es el último en la lista de bordes adyacentes. La implementación recursiva visitará los nodos del gráfico de ejemplo en el siguiente orden: A, B, D, F, E, C, G. La implementación no recursiva visitará los nodos como: A, E, F, B, D , C, G.
La implementación no recursiva es similar a la búsqueda de amplitud, pero difiere de ella de dos maneras:
- usa una pila en lugar de una cola, y
- retrasa la comprobación de si se ha descubierto un vértice hasta que se saca el vértice de la pila en lugar de realizar esta comprobación antes de agregar el vértice.
Aplicaciones [ editar ]
Los algoritmos que utilizan la búsqueda en profundidad como un bloque de construcción incluyen:
- Encontrar componentes conectados .
- Clasificación topológica .
- Encontrar componentes conectados al 2- (borde o vértice).
- Encontrar componentes 3- (borde o vértice) conectados.
- Encontrar el puentes de un gráfico.
- Generando palabras para trazar el conjunto de límites de de un grupo .
- Encontrar componentes fuertemente conectados .
- Prueba de planaridad . [7] [8]
- Resolver acertijos con una sola solución, como laberintos . (DFS se puede adaptar para encontrar todas las soluciones a un laberinto al incluir solo nodos en la ruta actual en el conjunto visitado).
- Generación de laberintos puede usar una búsqueda aleatoria de profundidad primero.
- Encontrar la biconnectividad en gráficos .
Complejidad [ editar ]
La complejidad computacional de la DFS fue investigado por John Reif . Más precisamente, dado un gráfico, dejar ser el orden calculado por el algoritmo DFS recursivo estándar. Este ordenamiento se denomina ordenamiento lexicográfico de búsqueda de profundidad primero. John Reif consideró la complejidad de calcular el orden lexicográfico de búsqueda de profundidad primero, dado un gráfico y una fuente. Una versión de decisión del problema (probar si algún vértice u ocurre antes de algún vértice v en este orden) es P- completo , [9] lo que significa que es "una pesadilla para el procesamiento paralelo ". [10] : 189
Un orden de búsqueda de profundidad primero (no necesariamente el lexicográfico) puede calcularse mediante un algoritmo paralelo aleatorio en la clase de complejidad RNC . [11] A partir de 1997, se desconoce si un primer algoritmo paralelo de determinación podría construir un recorrido en profundidad en la clase de complejidad NC .
Los algoritmos de búsqueda heurística incremental combinan tanto la búsqueda incremental como la heurística para acelerar las búsquedas de secuencias de problemas de búsqueda similares, lo cual es importante en dominios que solo se conocen de forma incompleta o cambian dinámicamente. [1] La búsqueda incremental se ha estudiado al menos desde finales de la década de 1960. Los algoritmos de búsqueda incremental reutilizan información de búsquedas anteriores para acelerar la búsqueda actual y resolver problemas de búsqueda potencialmente mucho más rápido que resolverlos repetidamente desde cero. [2] Del mismo modo, la búsqueda heurística también se ha estudiado al menos desde finales de la década de 1960.
Los algoritmos de búsqueda heurísticos, a menudo basados en A * , utilizan el conocimiento heurístico en forma de aproximaciones de las distancias objetivo para enfocar la búsqueda y resolver problemas de búsqueda potencialmente mucho más rápidos que los algoritmos de búsqueda no informados. [3] Los problemas de búsqueda resultantes, a veces llamados problemas de planificación dinámica de rutas, son problemas de búsqueda de gráficos en los que las rutas deben encontrarse repetidamente porque la topología del gráfico, sus costos de borde, el vértice de inicio o los vértices de meta cambian con el tiempo. [4]
Hasta ahora, se han desarrollado tres clases principales de algoritmos de búsqueda heurística incremental:
- La primera clase reinicia A * en el punto donde su búsqueda actual se desvía de la anterior (ejemplo: Fringe Saving A * [5] ).
- La segunda clase actualiza los valores h (heurísticos, es decir, la distancia aproximada a la meta) de la búsqueda anterior durante la búsqueda actual para que estén más informados (ejemplo: Adaptivo generalizado A * [6] ).
- La tercera clase actualiza los valores g (distancia desde el inicio) de la búsqueda anterior durante la búsqueda actual para corregirlos cuando sea necesario, lo que puede interpretarse como la transformación del árbol de búsqueda A * de la búsqueda anterior en el árbol de búsqueda A * para el búsqueda actual (ejemplos: Planificación de toda la vida A * , [7] D * , [8] D * Lite [9] ).
Las tres clases de algoritmos de búsqueda heurística incremental son diferentes de otros algoritmos de replanificación, como la planificación por analogía, en que la calidad de su plan no se deteriora con el número de episodios de replanificación.
No hay comentarios:
Publicar un comentario