20. Algoritmo Primero en Profundidad (DFS)

1. ¿Qué es DFS?

• Es un algoritmo de búsqueda no informada.
• Su objetivo es explorar un grafo (o árbol de estados) siguiendo un camino lo más profundo posible antes de retroceder.
• Se conoce como Depth First Search en inglés.

2. Estructuras de datos clave

• Agenda (estados abiertos):

  • Se implementa con una pila (stack).

  • Operaciones:

    • Agregar (push): insertar un estado en el tope.
    • Sacar (pop): extraer el último estado agregado.

  • Los estados en la agenda forman la frontera de búsqueda.

• Conjunto de estados expandidos (estados cerrados):

  • Se implementa con un hash set (tabla de dispersión).
  • Regla: un estado no se expande más de una vez.
  • Ventaja: verificar si un estado ya fue expandido toma tiempo constante, incluso con millones de estados.

3. Ejemplo práctico

• Agenda vacía → se agregan B, A, G, S.
• El tope es S.
• Al sacar: primero sale S, luego G, luego A…
• Así se va explorando en profundidad, siempre tomando el último estado agregado.

4. Idea central

• DFS avanza profundizando en un camino hasta que ya no puede continuar.
• Luego retrocede y explora otros caminos.
• La agenda (pila) marca lo que conocemos, y el hash set asegura que no repitamos estados.

5. Conceptos importantes

• Frontera de búsqueda: lo que está en la agenda, lo que conocemos.
• Horizonte desconocido: lo que está más allá de la frontera.
• Eficiencia: gracias al hash set, la verificación de estados es rápida.

👉 En resumen: DFS usa una pila para manejar los estados abiertos y un conjunto hash para los estados cerrados, explorando siempre en profundidad antes de retroceder.

---

En este ejemplo partimos de b y vemos cuales nodos tiene conectados B, entonces movemos B a la tabla de expandidos, anotamos los nodos que se puede ir desde B y continuamos iterando. G, A, S, H, siendo h nuestro top y por el cual iniciaremos a iterar a la hora de moverlo a expandidos pero tomando en cuenta que usamos un subíndice que contiene la letra de donde proviene para que este identificada en nuestro grafo.

Este proceso lo seguiremos haciendo hasta tener nuestra meta como a ==variable== de tope y tendremos una ruta que no suele ser la mas ==eficiente== pero si una ruta util para llegar de un punto A a un punto B. relatedInteligencia Artificial