Búsqueda en profundidad
La búsqueda en profundidad ( DFS ) es un algoritmo para recorrer 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 en la medida de lo posible a lo largo de cada rama antes de retroceder.
Una versión de la búsqueda en profundidad fue investigada en el siglo XIX por el matemático francés Charles Pierre Trémaux [1] como estrategia para resolver laberintos . [2] [3]
El análisis de tiempo y espacio de DFS difiere según su área de aplicación. En informática teórica, DFS se utiliza normalmente para recorrer un gráfico completo y lleva tiempo , [4] donde | V | es el número de vértices y | E | el número de aristas . Esto es lineal en el tamaño del gráfico. En estas aplicaciones, también utiliza el espacio en 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 en amplitud y la elección de cuál de estos dos algoritmos utilizar depende menos de su complejidad y más de las diferentes propiedades de los ordenamientos de vértices que producen los dos algoritmos.
Para 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 de 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 aristas expandidos (aunque este número no es el mismo que el tamaño de todo el gráfico porque algunos vértices se pueden buscar más de una vez y otros en absoluto), pero la complejidad del espacio de esta variante de DFS es solo proporcional al límite de profundidad y, como resultado, es mucho más pequeño que el espacio necesario para buscar a la misma profundidad utilizando la búsqueda primero en amplitud. Para tales aplicaciones, DFS también se presta mucho mejor a métodos heurísticos para elegir una rama de apariencia probable. Cuando no se conoce a priori un límite de profundidad adecuado,La búsqueda iterativa de profundización primero 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 utilizar para recopilar una muestra de nodos de gráficos. Sin embargo, incompleta DFS, de manera similar a incompletas BFS , está sesgada hacia los nodos de alto grado .
una búsqueda en profundidad que comienza en el nodo A, asumiendo que los bordes izquierdos en el gráfico mostrado se eligen antes que los bordes derechos, y asumiendo 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. Las aristas atravesadas en esta búsqueda forman un árbol de Trémaux , una estructura con importantes aplicaciones en la teoría de grafos . Realizar la misma búsqueda sin recordar los nodos visitados anteriormente da como resultado visitar los nodos en el orden A, B, D, F, E, A, B, D, F, E, etc. para siempre, atrapados en A, B, D, Ciclo F, E y nunca llegar a C o G.
