Búsqueda en profundidad
La búsqueda primero en profundidad ( DFS ) es un algoritmo para atravesar o buscar estructuras de datos de árboles o gráficos . 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 lejos posible a lo largo de cada rama antes de retroceder. Se necesita memoria adicional, generalmente una pila , para realizar un seguimiento de los nodos descubiertos hasta el momento a lo largo de una rama específica, lo que ayuda a retroceder en el gráfico.
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 una 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 usa normalmente para recorrer un gráfico completo y lleva tiempo , [4] donde es el número de vértices y 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 primero en 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 el rastreo web, el gráfico que se va a recorrer suele ser demasiado grande para visitarlo en su totalidad o infinito (DFS puede no terminar ). 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 expandidas (aunque este número no es el mismo que el tamaño del gráfico completo porque algunos vértices pueden buscarse 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 en anchura. 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 a priori un límite de profundidad adecuado,la búsqueda iterativa de profundización primero 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 en 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áfico. Sin embargo, el DFS incompleto, al igual que el BFS incompleto , está sesgado hacia los nodos de alto grado .
