vivianamg2006-byte

Posted on Apr 25

Proyecto Laberintos - Generar y Resolver | Estructuras de Datos

#versionfinal

Datos del proyecto

Curso: Estructuras de Datos

Período: I Cuatrimestre 2026

Estudiantes: Nadia Gabriela Arauz Mayorga y Viviana Nicole Masís García
Problema: Laberintos (Generar y Resolver)

Descripción formal del problema

El sistema desarrollado debe:

Generar automáticamente un laberinto de tamaño n x m (mínimo 10×10) con paredes y caminos.
Resolver el laberinto encontrando un camino desde una entrada hasta una salida.
Comparar al menos dos algoritmos de resolución (BFS vs DFS).
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)

Clase	Responsabilidad
`Nodo`	Almacena una posición (fila, columna) y punteros siguiente/anterior para ser usado en Pila y Cola.
`Pila`	Estructura lineal LIFO usada en la generación del laberinto (DFS carving) y en la resolución con DFS.
`Cola`	Estructura lineal FIFO usada en la resolución con BFS (camino más corto).
`Laberinto`	Contiene la lógica principal: generar, resolver, mostrar, medir métricas.
`main`	Controla el menú interactivo y la entrada del usuario.

Estructuras de datos utilizadas y justificación

Estructura	Uso	¿Por qué?	Complejidad (acceso/operación)
Matriz 2D (`vector<vector<char>>`)	Representa las celdas del laberinto	Acceso directo por coordenadas en O(1), visualización sencilla	O(1) lectura/escritura
Cola (implementación manual doblemente enlazada)	BFS para encontrar la ruta más corta	BFS requiere FIFO para explorar por niveles	O(1) encolar/desencolar
Pila (implementación manual doblemente enlazada)	Generación del laberinto (DFS carving) y resolución DFS	LIFO natural para backtracking en generación y exploración en profundidad	O(1) push/pop
`vector<vector<Posicion>>` (matriz de padres)	Reconstrucción de la ruta después de BFS/DFS	Guarda el nodo predecesor de cada celda → reconstrucción del camino al final	O(1) acceso, reconstrucción O(longitud ruta)

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)

Algoritmo	Tiempo (peor caso)	Espacio (peor caso)	Explicación
Generación (DFS carving)	O(filas × columnas)	O(filas × columnas)	Cada celda se visita una vez. La pila puede llegar a guardar O(n×m) celdas en el peor caso.
BFS	O(filas × columnas)	O(filas × columnas)	Explora todas las celdas hasta encontrar la salida. La cola puede contener muchas celdas en la frontera.
DFS	O(filas × columnas)	O(filas × columnas)	Similar a BFS; la pila también puede crecer hasta el número de celdas.

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

Métricas experimentales (reales)

Ejecución realizada: Laberinto de 15×15, entrada en fila 1, salida en fila 13.

Semilla: 42 (fija para reproducibilidad). Las métricas se obtuvieron directamente del programa.

Algoritmo	Celdas exploradas	Longitud de ruta	Tiempo (ms)
BFS	51	20	0.2914
DFS	21	20	0.1541

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)

Criterio	BFS	DFS
Camino más corto	Sí garantiza	No garantiza (pero a veces da igual)
Memoria	Cola (puede ser grande)	Pila (generalmente menor)
Tiempo en la práctica	Similar o ligeramente mayor	Ligeramente menor (en promedio)
Implementación	Cola + visitados + padres	Pila + visitados + padres
Útil cuando…	Se necesita la ruta óptima	Solo importa encontrar cualquier camino, o la memoria es limitada

Conclusión de la comparación:

Implementamos ambos algoritmos. En nuestras pruebas, BFS exploró más celdas pero fue más confiable para encontrar la ruta óptima. DFS fue más rápido en tiempo y memoria, aunque en otros laberintos podría dar rutas más largas. Cada uno tiene su utilidad según el objetivo.

Interfaz de usuario (consola)

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

MENÚ DE LABERINTOS

Definir tamaño del laberinto
Generar laberinto
Mostrar laberinto
Resolver con BFS
Resolver con DFS
Comparar BFS vs DFS
Reiniciar
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

Validación	Implementación
Dimensiones mínimas (10×10)	`definirTamanio()` retorna `false` si filas < 10 o columnas < 10, y el menú repite la pregunta.
Entrada y salida dentro del tablero	`asignarEntradaSalida()` busca celdas `'.'` en la fila 1 (entrada) y fila `filas-2` (salida).
Entrada y salida transitables (no pared)	Solo se eligen celdas donde `mapa[1][j] == '.'` y `mapa[filas-2][j] == '.'`.
Laberinto sin solución	Si BFS o DFS no encuentran camino, muestran `"No se encontró solución"`. El usuario puede reiniciar o regenerar con otra semilla.
Laberinto inválido (sin conexión)	El algoritmo DFS carving produce un laberinto perfecto conectado. Si entrada y salida quedan en componentes distintos, se reporta y el usuario puede regenerar.

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:

"Que es un dfs craving en c++? en español"
Respuesta:
"para que se usan los archivos .h?"
Respuesta:
"En c++, recomiendas usar las librerias de stack y queu o es mejor hacer las clases por separado ?"
Respuesta:
"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

Generación con DFS carving es eficiente (O(n×m)) y produce laberintos perfectos sin ciclos, ideales para el problema.
BFS garantiza la ruta más corta en número de pasos, aunque puede explorar más celdas y ser ligeramente más lento.
DFS es más rápido en memoria y tiende a explorar menos celdas cuando encuentra una ruta pronto, pero no asegura optimalidad.
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.
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.

DEV Community