🌸 3.8.1 BÚSQUEDA DE METAS A PROFUNDIDAD (DFS)

 

   Fundamento teórico

La búsqueda en profundidad (Depth First Search, DFS) es un algoritmo de búsqueda que explora un camino lo más profundo posible antes de retroceder y probar otros caminos.

Este método utiliza una estructura de tipo pila (stack), ya sea explícita o mediante recursión, para recorrer los nodos del espacio de estados.

DFS se utiliza cuando se desea explorar completamente una rama antes de cambiar a otra, lo que lo hace útil en problemas donde las soluciones pueden estar en niveles profundos.

Ejemplo:
Resolver un laberinto siguiendo un camino hasta el final antes de retroceder si no hay salida.

Características principales

• 📌 Explora profundamente cada rama.
• 📌 Usa estructura tipo pila.
• 📌 No garantiza la solución óptima.
• 📌 Puede quedar atrapado en caminos largos.
• 📌 Requiere poca memoria.

 Importancia

• Útil para explorar soluciones profundas.
• Base de muchos algoritmos recursivos.
• Eficiente en memoria.

 Ventajas

• Bajo consumo de memoria.
• Fácil implementación.
• Útil en estructuras profundas.

 Limitaciones

• Puede no encontrar la solución óptima.
• Puede entrar en bucles infinitos.
• No es eficiente en todos los casos.

 Aplicaciones

• Resolución de laberintos
• IA en juegos
• Análisis de grafos
• Compiladores

Video explicativo:

Práctica:

Actividad: Simulación DFS

Dibuja un árbol de 6 nodos y simula cómo DFS lo recorrería.

📄 Ver práctica en PDF

 Evaluación:

1. ¿Qué es DFS?
2. ¿Qué estructura utiliza?
3. ¿Cuál es su principal ventaja?
4. ¿Qué problema puede presentar?
5. Da un ejemplo de uso.

 Conclusión:

DFS es un algoritmo de búsqueda profundo que permite explorar caminos completos en un espacio de estados, siendo útil pero no siempre óptimo.

Referencias APA 7

• Russell, S., & Norvig, P. (2021). Artificial intelligence: A modern approach.
• Cormen, T. et al. (2009). Introduction to algorithms.