Datos del proyecto

---

Descripción formal del problema

El sistema desarrollado debe:

1. Generar automáticamente un laberinto de tamaño n x m (mínimo 10×10) con paredes y caminos.
2. Resolver el laberinto encontrando un camino desde una entrada hasta una salida.
3. Comparar al menos dos algoritmos de resolución (BFS vs DFS).
4. Analizar la complejidad temporal y espacial.

El laberinto se modela como una matriz de celdas donde:

• # = pared
• . = camino transitable
• E = entrada
• S = salida
• * = ruta solución (cuando se resuelve)

---

Modelado estructural (clases)

---

Estructuras de datos utilizadas y justificación

Justificación adicional:

• Matriz 2D: opción natural para un laberinto basado en celdas. C++ con vector permite redimensionamiento dinámico y copia sencilla.
• Cola y Pila manuales: aunque existen std::queue y std::stack, implementarlas manualmente demuestra comprensión de estructuras lineales y permite control total sobre la memoria (punteros, sin realloc).
• Matriz de padres: alternativa más eficiente que std::map para las dimensiones usadas (acceso O(1) en lugar de O(log n)), aprovechando que las coordenadas son enteros pequeños.

---

Algoritmos implementados

1. Generación del laberinto (DFS recursive backtracking – “carving”)

• Inicializar todas las celdas como pared #.
• Elegir una celda inicial en una posición impar (ej. 1,1) y marcarla como camino ..
• Usar una pila para guardar la celda actual.
• Mientras la pila no esté vacía:
  • Obtener vecinos a dos pasos que sigan siendo pared.
  • Si hay vecinos: elegir uno al azar, derribar la pared intermedia, marcar el vecino como camino y apilarlo.
  • Si no hay vecinos: desapilar (retroceder).
• Forzar bordes como paredes para cerrar el laberinto.

Este método garantiza un laberinto perfecto (sin ciclos, con un único camino posible entre dos celdas).

2. Resolución con BFS (camino más corto)

• Usa cola (FIFO) para explorar nivel por nivel.
• Mantiene una matriz visitado y una matriz padre para reconstruir la ruta.
• Termina al encontrar la salida.
• Ventaja: siempre encuentra el camino con el menor número de pasos.

3. Resolución con DFS (camino no óptimo)

• Usa pila (LIFO) para explorar en profundidad.
• Similar a BFS en estructuras auxiliares, pero el orden de exploración es diferente.
• Desventaja: no garantiza la ruta más corta (aunque en el caso de prueba coincidió).

---

Análisis de complejidad teórica (Big-O)

En la práctica, para laberintos de 15×15 (225 celdas), cualquiera de los algoritmos es instantáneo.

---

Métricas experimentales (reales)

Discusión:

• Ambos algoritmos encontraron la misma longitud de ruta (20 pasos) en esta ejecución.
• BFS exploró más del doble de celdas (51 vs 21) porque revisa sistemáticamente todos los niveles antes de encontrar la salida.
• DFS fue más rápido (0.1541 ms frente a 0.2914 ms) porque exploró menos celdas y encontró una ruta válida rápidamente.
• Teóricamente, BFS garantiza la ruta más corta; aquí DFS también la encontró por casualidad debido a la estructura del laberinto.

---

Análisis de resultados

Con base en las métricas obtenidas para un laberinto de 15×15 con semilla 42, se observa:

• Ruta óptima: ambos algoritmos (BFS y DFS) encontraron la misma longitud de ruta (20 pasos). Esto significa que en este laberinto particular, DFS también halló la ruta más corta, aunque teóricamente no está garantizado.
• Eficiencia en exploración: BFS exploró 51 celdas, mientras que DFS solo 21. La diferencia se debe a que BFS explora por niveles y debe revisar todas las celdas a una distancia k antes de avanzar, mientras que DFS se "lanza" en profundidad y puede toparse con la salida más rápido si la rama elegida es la correcta.
• Tiempo de ejecución: DFS fue más rápido (0.1541 ms vs 0.2914 ms), coherente con la menor cantidad de celdas exploradas. La diferencia es pequeña (décimas de milisegundo) por el tamaño reducido del laberinto; en mapas más grandes (100×100 o más) la brecha sería más notoria.
• Confiabilidad: BFS es más confiable si se requiere la ruta más corta siempre. DFS puede ser útil cuando se prioriza la velocidad de respuesta y no importa que la ruta sea subóptima.

Estos resultados confirman las complejidades teóricas (O(n×m) para ambos) y muestran que, en la práctica, el comportamiento depende de la estructura del laberinto y de la posición de la entrada/salida.

---

Capturas de pantalla del proceso

Paso 1 – Definir tamaño y generar laberinto con semilla 42:

Paso 2 – Laberinto generado y menú:

Paso 3 – Resolución con BFS (ruta marcada con *):

Paso 4 – Resolución con DFS:

Paso 5 – Comparación de métricas:

---

Comparación de enfoques (BFS vs DFS)

---

Interfaz de usuario (consola)

El programa presenta un menú interactivo con las siguientes opciones:

MENÚ DE LABERINTOS

1. Definir tamaño del laberinto
2. Generar laberinto
3. Mostrar laberinto
4. Resolver con BFS
5. Resolver con DFS
6. Comparar BFS vs DFS
7. Reiniciar
8. Salir

• Opción 1: Permite ingresar filas y columnas (mínimo 10×10, con validación).
• Opción 2: Genera el laberinto usando DFS carving. Se puede ingresar una semilla para reproducibilidad (-1 = aleatorio).
• Opción 3: Muestra el laberinto actual con la leyenda.
• Opción 4: Resuelve con BFS, muestra la ruta marcada con * y las métricas.
• Opción 5: Resuelve con DFS.
• Opción 6: Ejecuta ambos y muestra una tabla comparativa.
• Opción 7: Reinicia el laberinto (pide nuevas dimensiones y genera uno nuevo automáticamente).
• Opción 8: Sale del programa.

---

Validaciones implementadas

Además, se realiza validación de entrada del usuario (tamaños), control de estados visitados para evitar ciclos en BFS/DFS, y restauración del mapa original antes de cada resolución.

---

Uso de Inteligencia Artificial

Herramienta utilizada: DeepSeek (modelo de lenguaje)

Objetivo del uso: Comprensión conceptual y apoyo en la documentación.

Prompts empleados y respuestas:

1. "Que es un dfs craving en c++? en español"
   Respuesta:
   

2. "para que se usan los archivos .h?"
   Respuesta:
   

3. "En c++, recomiendas usar las librerias de stack y queu o es mejor hacer las clases por separado ?"
   Respuesta:
   

4. "Si implemento una semilla aleatoria después de dar dimensiones en un programa de laberintos, es posible que no me dé una solución?"
   Respuesta:
   

Links de las conversaciones
Nadia: https://chat.deepseek.com/share/bsay04pct5cnhmav6k
Viviana: https://chat.deepseek.com/share/biigrbtsxjqilqmzz2

Cómo ayudó en la investigación:

• Aclaró conceptos de backtracking y algoritmos de búsqueda en grafos.
• Proporcionó ejemplos de pseudocódigo adaptables a C++.
• Ayudó a organizar la comparación entre BFS y DFS de forma clara.
• Explicó la importancia de la semilla y los casos sin solución.

Modificaciones realizadas:

• Adaptación completa a C++ con gestión manual de memoria (pilas y colas con new/delete).
• Implementación propia de la matriz de padres (sin usar std::map).
• Diseño completo de la interfaz por consola y menú iterativo.
• Inclusión de validación de tamaño mínimo y opción de reinicio completo.

---

Conclusiones técnicas

1. Generación con DFS carving es eficiente (O(n×m)) y produce laberintos perfectos sin ciclos, ideales para el problema.

2. BFS garantiza la ruta más corta en número de pasos, aunque puede explorar más celdas y ser ligeramente más lento.

3. DFS es más rápido en memoria y tiende a explorar menos celdas cuando encuentra una ruta pronto, pero no asegura optimalidad.

4. La combinación matriz + cola/pila + matriz de padres es suficiente y eficiente para laberintos de hasta cientos de celdas, sin necesidad de estructuras más complejas.

5. El sistema cumple todos los puntos solicitados: generación, resolución con ambos algoritmos, comparación, métricas, validaciones, reinicio, menú interactivo y uso explícito de estructuras lineales y no lineales.

---

Proyecto elaborado para el curso de Estructuras de Datos, I Cuatrimestre 2026.