Clase 36 de 52 • Curso de Algoritmos Avanzados: Grafos y Árboles
Contenido del curso
Grafos y Árboles: Estructuras de Datos Avanzadas
Estructuras de Datos: Introducción a Árboles y Sus Propiedades
Recursión: Concepto y Aplicaciones Prácticas con Ejemplos
Aplicaciones Prácticas de Grafos en Tecnología e Industria
Representación de Grafos: Matriz y Lista de Adyacencia
Búsqueda en Profundidad (DFS) en Árboles y Grafos
Implementación de DFS recursivo para búsqueda en árboles
Búsqueda en Profundidad (DFS) para Grafos: Enfoque Iterativo y Recursivo
Recorridos y Profundidad en Árboles Binarios y Enearios
Suma de Caminos en Árboles Binarios
Suma de Números de Raíz a Hoja en Árboles
Playground: Sum Root to Leaf Numbers
Implementación de Algoritmo DFS en Árboles Binarios con Golang
Resolución del Problema de Número de Islas con DFS
Conteo de Islas en Matrices con DFS
Playground: Number of Islands
Implementación de "Número de Islas" con Recursión en Python
Ejercicios Prácticos de Búsqueda en Profundidad (DFS)
Algoritmos de Búsqueda en Profundidad (DFS) en Problemas Comunes
Algoritmo BFS: Recorrido en Anchura de Grafos y Árboles
Implementación de BFS en Árboles usando Python
Movimiento mínimo de caballo en ajedrez infinito
Resolviendo el Problema Mínimo de Movimiento del Caballo en Ajedrez
Playground: Minimum Knights Moves
Resolución de Problemas de Caballos de Ajedrez con BFS en Python
Propagación de Plagas en Cultivos: Cálculo de Días para Contagio Total
Resolución de Rotting Oranges usando BFS
Playground: Rotting Oranges
Propagación de Plagas en Matrices usando BFS en Java
Construcción de Puentes Cortos entre Islas en Matrices Binarias
Resolución del Problema Shortest Bridge con DFS y BFS
Playground: Shortest Bridge Between Islands
Búsqueda del camino más corto entre islas usando BFS en Python
Búsqueda en anchura: Ejercicios prácticos y aplicaciones
Ejercicios avanzados de búsqueda en anchura (BFS) en programación
Algoritmo Backtracking: Solución de Problemas Complejos
Combinaciones de Letras en Números Telefónicos
Combinaciones de Letras a partir de un Número de Teléfono
Generación de combinaciones de letras con teclados numéricos en C++
Playground: Letter Combinations of a Phone Number
Generación de Direcciones IP Válidas a partir de Cadenas Numéricas
Generación de IPs válidas con backtracking en C++
Playground: Restore IP Addresses
Búsqueda de Palabras en Matrices: Solución y Complejidad
Búsqueda de Palabras en Matrices usando Backtracking y DFS
Playgrund: Word Search
Implementación de búsqueda de palabras en matrices con DFS en JavaScript
Resolución del problema de las n reinas en ajedrez
Ejercicios de Backtracking: Combinaciones y Permutaciones
Combinaciones y Permutaciones con Backtracking
El algoritmo de Backtracking es una técnica poderosa y, a menudo, subestimada en el mundo de la programación y la computación. Imagina que te encuentras en un laberinto y necesitas encontrar la salida. Comienzas a caminar, te encuentras con un obstáculo, retrocedes hasta el último punto donde tenías múltiples opciones y sigues avanzando. Este enfoque se aplica de manera similar en problemas computacionales, donde se intenta y retrocede hasta encontrar la solución correcta sin insistir en caminos que conducen a un callejón sin salida.
Fuerza bruta: Este método implica explorar todas las opciones posibles para encontrar la solución. Por ejemplo, en un laberinto, significa chocar contra todas las paredes y caminos posibles hasta que eventualmente encuentras la salida. Aunque efectivo, suele ser ineficiente por su extenso consumo de tiempo y recursos.
Backtracking: Este enfoque se enfoca en identificar y descartar caminos no viables lo antes posible. Cuando un camino se demuestra inviable, se retrocede y se exploran otras opciones. Así, se puede llegar a una solución más rápidamente sin probar exhaustivamente cada posibilidad.
Utiliza el algoritmo de Backtracking en problemas que requieran todas las combinaciones posibles pero sin el gasto de energía en soluciones inviables. Ejemplos destacados son:
Problema de las n-reinas: Un problema clásico de ajedrez donde se debe posicionar reinas en un tablero sin que se ataquen entre ellas. Aquí, Backtracking ayuda a encontrar todas las soluciones posibles sin validar combinaciones enteras con errores desde el principio.
Generación de subconjuntos: Cuando se requiere listar todas las posibles combinaciones de un conjunto de elementos, el backtracking es ideal para evitar duplicaciones innecesarias y reducir la carga de cálculo.
Estos conceptos reflejan la esencia del Backtracking: intentar un camino y, si encuentras un obstáculo, retroceder y probar una nueva ruta. Así, se optimiza el proceso de resolución de problemas complejos. ¡Anímate a implementar Backtracking en tus propias soluciones y observa cómo simplifica problemas complejos de manera elegante y eficiente!
