Introducción a la clase
En esta clase exploraremos dos técnicas avanzadas en la resolución de problemas: programación dinámica y backtracking. Estas estrategias se utilizan para resolver problemas complejos de manera eficiente, reduciendo el número de cálculos innecesarios o explorando múltiples soluciones de manera ordenada.
¿Qué obtendrás de esta clase?
- Comprender qué es la programación dinámica y su aplicación en problemas de optimización.
- Aprender sobre backtracking y cómo se usa para resolver problemas de búsqueda y combinaciones.
- Implementar algoritmos de programación dinámica y backtracking en C#.
- Aplicar estos algoritmos en casos reales.
Programación Dinámica
La programación dinámica (DP) es una técnica de optimización que almacena resultados intermedios para evitar cálculos repetitivos en problemas que tienen una subestructura óptima y superposición de subproblemas.
Ejemplo de Problema: Serie de Fibonacci
El cálculo de la Serie de Fibonacci es un caso clásico donde almacenar resultados intermedios reduce significativamente el número de cálculos.
Implementación Recursiva Sin Programación Dinámica (Ineficiente – O(2ⁿ))
using System;
class Program
{
static int Fibonacci(int n)
{
if (n <= 1) return n;
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
static void Main()
{
Console.WriteLine("Ingrese un número para calcular Fibonacci:");
int n = Convert.ToInt32(Console.ReadLine());
Console.WriteLine($"Fibonacci({n}) = " + Fibonacci(n));
}
}
Esta implementación es ineficiente, ya que recalcula valores repetidamente.
Implementación con Programación Dinámica (Eficiente – O(n))
using System;
using System.Collections.Generic;
class Program
{
static Dictionary<int, long> memo = new Dictionary<int, long>();
static long FibonacciDP(int n)
{
if (n <= 1) return n;
if (!memo.ContainsKey(n))
memo[n] = FibonacciDP(n - 1) + FibonacciDP(n - 2);
return memo[n];
}
static void Main()
{
Console.WriteLine("Ingrese un número para calcular Fibonacci:");
int n = Convert.ToInt32(Console.ReadLine());
Console.WriteLine($"Fibonacci({n}) = " + FibonacciDP(n));
}
}
Aquí, almacenamos los resultados previos en un diccionario, reduciendo los cálculos innecesarios.
Backtracking
El backtracking es una técnica utilizada para resolver problemas de búsqueda y combinaciones explorando todas las soluciones posibles y retrocediendo cuando una opción no es válida.
Ejemplo de Problema: Sudoku o el Problema de la Mochila
Un ejemplo clásico es el Problema de la N-Queens, donde debemos colocar N reinas en un tablero de ajedrez sin que se ataquen entre sí.
Implementación del Problema de la N-Queens en C#
using System;
class NQueens
{
static int N = 8;
static int[,] tablero = new int[N, N];
static bool EsSeguro(int fila, int col)
{
for (int i = 0; i < col; i++)
if (tablero[fila, i] == 1) return false;
for (int i = fila, j = col; i >= 0 && j >= 0; i--, j--)
if (tablero[i, j] == 1) return false;
for (int i = fila, j = col; i < N && j >= 0; i++, j--)
if (tablero[i, j] == 1) return false;
return true;
}
static bool ResolverNQueens(int col)
{
if (col >= N) return true;
for (int i = 0; i < N; i++)
{
if (EsSeguro(i, col))
{
tablero[i, col] = 1;
if (ResolverNQueens(col + 1)) return true;
tablero[i, col] = 0;
}
}
return false;
}
static void ImprimirTablero()
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
Console.Write(tablero[i, j] + " ");
Console.WriteLine();
}
}
static void Main()
{
if (ResolverNQueens(0))
ImprimirTablero();
else
Console.WriteLine("No hay solución");
}
}
Este código utiliza backtracking para encontrar una disposición válida de las N reinas en un tablero de ajedrez.
Comparación entre Programación Dinámica y Backtracking
| Característica | Programación Dinámica | Backtracking |
|---|---|---|
| Uso principal | Optimización de problemas con subestructura óptima | Búsqueda de soluciones mediante exploración |
| Enfoque | Almacenar resultados previos para evitar cálculos repetidos | Explorar todas las soluciones posibles y retroceder cuando sea necesario |
| Complejidad | Generalmente O(n) o O(n²) | Puede ser O(2ⁿ) o peor |
| Aplicaciones comunes | Fibonacci, Problema de la Mochila, Caminos en matrices | Sudoku, N-Queens, Generación de combinaciones |
Caso de uso real
Un sistema de recomendación de rutas puede usar programación dinámica para encontrar el camino más corto entre dos puntos almacenando caminos previos.
Un algoritmo de inteligencia artificial en juegos usa backtracking para evaluar todas las posibles jugadas antes de tomar una decisión.
Ejemplo en C#: Ruta más corta usando Programación Dinámica
using System;
class Program
{
static int Minimo(int a, int b, int c) => Math.Min(a, Math.Min(b, c));
static int CaminoMasCorto(int[,] grid, int filas, int cols)
{
int[,] dp = new int[filas, cols];
dp[0, 0] = grid[0, 0];
for (int i = 1; i < filas; i++)
dp[i, 0] = dp[i - 1, 0] + grid[i, 0];
for (int j = 1; j < cols; j++)
dp[0, j] = dp[0, j - 1] + grid[0, j];
for (int i = 1; i < filas; i++)
for (int j = 1; j < cols; j++)
dp[i, j] = grid[i, j] + Minimo(dp[i - 1, j], dp[i, j - 1], dp[i - 1, j - 1]);
return dp[filas - 1, cols - 1];
}
static void Main()
{
int[,] grid = {
{ 1, 3, 1 },
{ 1, 5, 1 },
{ 4, 2, 1 }
};
Console.WriteLine("El camino más corto tiene costo: " + CaminoMasCorto(grid, 3, 3));
}
}
Este algoritmo encuentra el camino más corto en una cuadrícula usando programación dinámica.
Próxima clase: Aplicaciones de estructuras de datos en la vida real
En la siguiente clase exploraremos casos reales donde se aplican las estructuras de datos, incluyendo bases de datos, redes sociales, sistemas de recomendación y más.
