Clase 3 — Métodos Exactos vs. Heurísticos en Optimización
Resumen Ejecutivo
La sesión abordó la clasificación de algoritmos de optimización, distinguiendo entre métodos exactos (que garantizan el óptimo global pero a un coste computacional elevado) y métodos heurísticos (que encuentran buenas soluciones en tiempo razonable sin garantizar el óptimo). Se repasaron técnicas exactas como la búsqueda exhaustiva, backtracking y cribado, y se introdujo el panorama de las metaheurísticas bioinspiradas que se desarrollarán en las próximas sesiones.
Conceptos Clave
- Algoritmo exacto: Método que garantiza encontrar la solución óptima global del problema. ⚠️ EXAMEN
- Algoritmo heurístico: Método que encuentra una buena solución en tiempo razonable, sin garantizar el óptimo global. ⚠️ EXAMEN
- Metaheurística: Combinación de dos o más heurísticas para reducir la probabilidad de quedar atrapado en un óptimo local. ⚠️ EXAMEN
- Óptimo local vs. global: Un óptimo local es el mejor valor en una vecindad; el global es el mejor en todo el espacio de búsqueda. ⚠️ EXAMEN
- Búsqueda exhaustiva (fuerza bruta): Evaluar todas las combinaciones posibles; es un tipo de algoritmo exacto, no sinónimo de "exacto". ⚠️ EXAMEN
- Backtracking: Exploración por ramas que retrocede al encontrar caminos inválidos.
- Cribado: Reducción del espacio de búsqueda mediante filtros sucesivos.
- Complejidad P/NP/NP-Hard: P = resoluble en tiempo polinómico; NP = verificable en tiempo polinómico; NP-Hard = al menos tan difícil como cualquier problema NP.
- Notación Big O: Mide el crecimiento asintótico del número de operaciones cuando la entrada tiende a infinito.
Desarrollo del Temario
1. Repaso de complejidad computacional y la Máquina de Turing
La Máquina de Turing es el modelo teórico que fundamenta cómo medimos la complejidad computacional. Consta de: 1. Una cinta dividida en celdas con símbolos (que evolucionan a 0s y 1s). 2. Una cabeza lectora/escritora que se desplaza por la cinta. 3. Un conjunto de reglas (tarjetas) que dictan el comportamiento: según el símbolo leído, la cabeza escribe, se mueve a izquierda o derecha, y pasa a otra tarjeta.
La relación con la Big O es directa: \(T(n)\) cuenta el número de operaciones, y la Big O retiene solo el término de mayor crecimiento cuando \(n \to \infty\).
Formas de medir el rendimiento: - Análisis empírico: Ejecutar el mismo problema en distintas máquinas y comparar tiempos reales. - Caso promedio: Rendimiento esperado con entradas típicas (lo más relevante en la práctica). - Caso límite (peor caso): Lo que mide la Big O; cuando la entrada crece al infinito. ⚠️ EXAMEN
2. Clasificación de problemas: P, NP, NP-Hard
- P: Problemas resolubles en tiempo polinómico.
- NP: Problemas cuya solución es verificable en tiempo polinómico (no necesariamente resoluble en tiempo polinómico). ⚠️ EXAMEN
- NP-Hard: Problemas al menos tan difíciles como cualquier NP; si aumentas la entrada, se vuelven computacionalmente inviables.
Ejemplo: Un problema con variables enteras y un espacio de búsqueda grande tiende a ser NP. Si al aumentar el número de variables de entrada se vuelve intratable, probablemente sea NP-Hard. En variables continuas es más raro llegar a NP.
3. Algoritmos exactos
Garantizan encontrar el óptimo global, pero a costa de un alto coste computacional. La definición moderna ha evolucionado de "encontrar el óptimo perfecto" a "la mejor solución posible" dado el límite de cómputo y precisión numérica.
Principales algoritmos exactos:
| Algoritmo | Descripción |
|---|---|
| Programación lineal (Simplex) | Para problemas con función objetivo y restricciones lineales |
| Branch and Bound | Ramifica y acota; especialmente útil para variables enteras |
| Programación dinámica | Enfoque recursivo, descompone en subproblemas |
| Búsqueda exhaustiva | Prueba TODAS las combinaciones posibles (el peor computacionalmente) |
| Punto interior | Atraviesa el centro del poliedro factible en vez de las aristas; muy rápido pero requiere cálculo de inversas matriciales |
La búsqueda exhaustiva es UN TIPO de algoritmo exacto, no es sinónimo de algoritmo exacto. ⚠️ EXAMEN
4. Técnicas de reducción del espacio de búsqueda
4.1 Backtracking
Explora soluciones parciales como un árbol de decisiones. Si una rama viola las restricciones, retrocede (back) y prueba otra rama. Reduce drásticamente el espacio frente a la búsqueda exhaustiva.
Ejemplo — Sudoku: El algoritmo va casilla por casilla intentando colocar números del 1 al 9. Coloca un número, verifica las reglas (fila, columna, cuadrado 3×3). Si cumple, avanza. Si ningún número es válido, retrocede a la casilla anterior y prueba el siguiente número. Sin backtracking, un Sudoku tiene \(6.67 \times 10^{21}\) combinaciones posibles.
Ejemplo — N-Reinas: En un tablero \(N \times N\), colocar \(N\) reinas sin que se ataquen entre sí. Se coloca una reina por fila; si en una fila no hay posición válida, se retrocede a la fila anterior y se reubica esa reina.
4.2 Cribado (filtrado)
Reduce el espacio de búsqueda aplicando filtros sucesivos antes de explorar.
Ejemplo — Criba de Eratóstenes: Para encontrar números primos hasta \(N\): se toma el 2, se marcan todos sus múltiplos como no primos. Luego se toma el 3, se calcula \(3^2 = 9\) y se eliminan los múltiplos a partir de ahí. Luego el 5, \(5^2 = 25\), y así sucesivamente. No se prueban todos los números, se van eliminando sistemáticamente.
Comparativa de eficiencia: Cribado > Backtracking > Búsqueda exhaustiva ⚠️ EXAMEN
5. Algoritmos heurísticos
No garantizan el óptimo, pero encuentran una buena solución en tiempo razonable. ⚠️ EXAMEN
Nacen por la necesidad de resolver problemas NP-Hard donde los métodos exactos son inviables.
La palabra "heurística" viene del griego: encontrar o descubrir.
5.1 Búsqueda local (un solo punto de inicio)
El algoritmo parte de un punto y se mueve hacia soluciones vecinas mejores.
- Hill Climbing: Avanza siempre hacia el vecino con mejor valor. Se detiene cuando no encuentra mejora → riesgo de quedar atrapado en óptimo local. ⚠️ EXAMEN
- Simulated Annealing: Inspirado en el enfriamiento de metales; acepta soluciones peores con cierta probabilidad para escapar de óptimos locales.
- Búsqueda Tabú (Taboo Search): Mantiene una lista de movimientos prohibidos para evitar ciclos.
5.2 Métodos poblacionales (múltiples puntos de inicio)
Múltiples soluciones exploran el espacio simultáneamente y se comunican entre sí.
- Algoritmos evolutivos/genéticos: Inspirados en la selección natural.
- Enjambre (adaptación social): Colonias de hormigas, enjambre de partículas, etc.
Ejemplo de comunicación poblacional: Si hay varios puntos explorando y uno encuentra un valor de 1500 (maximizando) mientras los demás tienen 90, 10, 20, todos "saben" que 1500 es el mejor y se orientan hacia esa zona.
Ventaja de los poblacionales: Al explorar múltiples regiones simultáneamente, tienen menos probabilidad de quedar atrapados en un óptimo local. ⚠️ EXAMEN
5.3 Heurísticas vs. Metaheurísticas
- Heurística: Aplica una única estrategia de búsqueda.
- Metaheurística: Combina dos o más heurísticas para mejorar el rendimiento. ⚠️ EXAMEN
Ejemplo: En lugar de iniciar con un punto aleatorio, se usa primero un algoritmo voraz (greedy) para obtener una solución rápida inicial, y luego se aplica una búsqueda local o poblacional para optimizarla. Otra combinación: empezar con búsqueda local + aleatorio, encontrar una solución, y luego combinar con un método poblacional.
En la literatura actual, el término "metaheurística" se usa de forma casi intercambiable con "heurística".
6. Diferencia entre aproximado y heurístico
- Algoritmo aproximado: Es esencialmente un algoritmo exacto con un criterio de convergencia. El óptimo real podría ser \(1.999999\), pero el algoritmo para en \(1.9\) porque la mejora es despreciable. ⚠️ EXAMEN
- Algoritmo heurístico: No se basa en la matemática estricta del problema; usa estrategias creativas e inspiradas en la naturaleza.
La profesora señaló que esta diferencia es muy sutil y en la práctica podría considerarse al aproximado como un subtipo de exacto con criterio de parada.
7. Estrategia práctica para elegir algoritmo
- Leer el problema: identificar tipo de variables (continuas, enteras, mixtas), tamaño del espacio de búsqueda.
- Buscar problemas similares ya resueltos en la literatura.
- Seleccionar una familia de algoritmos apropiada y adaptar.
- Si hay problemas de rendimiento, evolucionar hacia variantes más eficientes.
Ejemplo de la profesora: Empezó con Simplex → migró a Punto Interior (más rápido) → para variables enteras usó Branch and Bound → evolucionó a métodos de planos de corte según la necesidad.
Preguntas de Autoevaluación
- ¿Cuál es la diferencia fundamental entre un algoritmo exacto y un algoritmo heurístico en cuanto a la garantía de solución?
- ¿Por qué la búsqueda exhaustiva (fuerza bruta) es solo un tipo de algoritmo exacto y no un sinónimo?
- Explica cómo funciona el backtracking usando el ejemplo del Sudoku o las N-Reinas.
- ¿Qué es la Criba de Eratóstenes y por qué se considera un método de cribado más eficiente que la búsqueda exhaustiva?
- ¿Qué problema tienen los algoritmos de búsqueda local como el Hill Climbing? ¿Cómo lo resuelven los métodos poblacionales?
- ¿Cuál es la diferencia entre una heurística y una metaheurística? Pon un ejemplo de combinación.
- Explica la diferencia entre un algoritmo aproximado y uno heurístico según las definiciones vistas en clase.
- ¿Qué tipos de variables (continuas vs. enteras) tienen mayor probabilidad de generar problemas NP-Hard y por qué?
- ¿Qué mide la notación Big O y por qué se centra en el caso límite en lugar del caso promedio?
- En un método poblacional, ¿cómo se comunican las soluciones entre sí para evitar óptimos locales?
Guía generada automáticamente a partir de transcripción con faster-whisper + Claude Opus 4.6.