AALIE

Comparación de Técnicas Algorítmicas

Síntesis para elegir técnica según la estructura del problema, las garantías requeridas y el costo esperado.

Idea central: no se elige la técnica por gusto

La técnica algorítmica no se elige por moda ni por comodidad. Se elige porque el problema tiene una estructura que la justifica: subproblemas independientes, subproblemas repetidos, decisiones locales seguras, restricciones parciales, cotas o búsqueda exhaustiva.

Principio de selección

Primero se identifica la estructura del problema; después se decide la técnica. Hacerlo al revés suele producir algoritmos que parecen sofisticados pero no están justificados.

Señales estructurales y técnica sugerida

Señal estructural	Pregunta diagnóstica	Técnica candidata
Costo acumulado por instrucciones repetidas	¿El algoritmo se explica principalmente por ciclos?	Análisis iterativo
Problema se divide en partes independientes	¿Los subproblemas no comparten resultados?	Divide y Vencerás
Problema se reduce a una versión más pequeña	¿Cada paso reduce el tamaño y continúa con un subproblema?	Resta y Vencerás / recursión lineal
Subproblemas repetidos	¿El mismo estado se calcula varias veces?	Programación Dinámica
Elección local segura	¿Se puede demostrar que escoger lo mejor ahora no daña el óptimo?	Voraz
Soluciones parciales bajo restricciones	¿Puedo podar una rama apenas viola una restricción?	Backtracking
Optimización con cotas	¿Puedo estimar si una rama ya no puede mejorar la mejor solución?	Branch and Bound
No hay estructura explotable	¿Solo queda probar todas las posibilidades?	Fuerza bruta

Modelo de decisión para elegir técnica

Una forma disciplinada de elegir técnica es responder preguntas en cascada. Cada pregunta descarta técnicas que no corresponden.

Modelo de selección de técnica

T ec ni c a (P) = ⎩ ⎨ ⎧ Iterativa, Divide y Vencer \overset{a}{ˊ} s, Resta y Vencer \overset{a}{ˊ} s, Programaci \overset{o}{ˊ} n Din \overset{a}{ˊ} mica, Voraz, Backtracking, Branch and Bound, Fuerza Bruta, P se resuelve por acumulaci \overset{o}{ˊ} n de pasos en ciclos P \to subproblemas independientes P \to un subproblema menor dominante P \to subproblemas superpuestos P \to elecci \overset{o}{ˊ} n local segura demostrable P \to decisiones reversibles con poda por factibilidad P \to optimizaci \overset{o}{ˊ} n con cotas de poda sin estructura explotable clara

Este modelo clasifica el problema P según su naturaleza estructural. La clave es identificar la relación entre el problema original y sus subproblemas o decisiones. Por ejemplo, si un problema se divide en partes que no comparten información, la técnica lógica es Divide y Vencerás; si las decisiones son irreversibles y locales, es Voraz.

Flujo de selección de técnica

Renderizando diagrama...

Tabla comparativa global

Comparación global de técnicas algorítmicas

Técnica	Estructura que aprovecha	Tipo de decisión	Garantía	Costo típico
Análisis iterativo	Ciclos y conteo de operaciones.	No diseña; analiza ejecución.	Exacta si el conteo es correcto.	Suma de ejecuciones por línea.
Programación Dinámica	Subproblemas superpuestos y subestructura óptima.	Evaluar alternativas y guardar estados.	Óptima por principio de optimalidad.	#Estados x costo transición.
Voraz	Propiedad voraz y subestructura óptima.	Elegir locallocally sin retroceso.	Óptima solo si se demuestra.	O(n) o O(n log n).

Programación Dinámica vs Voraces

Programación Dinámica y Voraces aparecen en problemas de optimización, pero tienen una diferencia central: PD evalúa alternativas y guarda resultados; el voraz toma una decisión local y no vuelve atrás.

Diferencia formal

Dec i s i o n (P) = {max {o p c i o n_{1}, o p c i o n_{2}, \dots}, se l ecc i o na r_l oc a l (C), Programaci \overset{o}{ˊ} n Din \overset{a}{ˊ} mica Voraz

La diferencia radica en el momento de la verdad. En Programación Dinámica, el valor final se elige comparando ( $max$ ) los resultados de varias opciones. En un algoritmo Voraz, solo se ejecuta una función de selección local sobre el conjunto de candidatos actuales C, sin mirar qué otras opciones podrían haber sido mejores a largo plazo.

Fuerza Bruta vs Backtracking vs Branch and Bound

Fuerza bruta, backtracking y Branch and Bound trabajan sobre espacios combinatorios. La diferencia es cuándo se descarta una rama y por qué se descarta.

Modelo de descarte de ramas

d esc a r t a r (r ama) = ⎩ ⎨ ⎧ nunca antes de completar, si viola restricciones, si viola restricciones o no mejora el incumbente, Fuerza Bruta Backtracking Branch and Bound

Este modelo define la agresividad de la poda. Mientras que la Fuerza Bruta explora todo, el Backtracking descarta ramas inviables (poda por factibilidad). El Branch and Bound va más allá y también descarta ramas que, aunque sean viables, su potencial (cota) no es suficiente para superar la mejor solución ya encontrada (incumbente).

Recursión, Divide y Vencerás y Programación Dinámica

No toda recursión es Divide y Vencerás, y no toda recursión necesita Programación Dinámica. La pregunta clave es qué ocurre con los subproblemas.

Clasificación por subproblemas

S u b p ro b l e ma s (P) = ⎩ ⎨ ⎧ uno menor dominante, varios independientes, varios repetidos, Resta y Vencer \overset{a}{ˊ} s Divide y Vencer \overset{a}{ˊ} s Programaci \overset{o}{ˊ} n Din \overset{a}{ˊ} mica

La clasificación depende de cómo interactúan los subproblemas generados. Si el problema P se resuelve simplemente reduciendo su tamaño, es una resta. Si se fragmenta en partes que no se solapan, es una división. Si las partes aparecen repetidas en distintas ramas, estamos ante la señal inequívoca para aplicar Programación Dinámica.

Comparación de tiempo y memoria

El costo de una técnica no se resume en una única notación. Depende del número de estados, ramas, niveles, candidatos o instrucciones que realmente se procesan.

Modelos de costo por técnica

Iterativo

Costo basado en el conteo de ejecuciones de cada línea de código.

T (n) = l in e a \sum cos t o (l in e a) \cdot v eces (l in e a)

Programación Dinámica

Cada estado único se calcula una sola vez gracias a la memoria.

T (n) = # es t a d os \cdot cos t o_t r an s i c i o n

Backtracking

Depende de cuántos nodos del árbol de decisiones se exploran realmente.

T (n) = N_{v i s i t a d os} \cdot C_{v a l i d a r}

Resumen operativo

Receta mínima

Analiza la estructura del problema antes de codificar.
Si hay ciclos, cuenta pasos.
Si hay subproblemas independientes, usa Divide y Vencerás.
Si hay subproblemas repetidos, usa Programación Dinámica.
Si hay una elección local segura demostrable, usa Voraz.
Si hay restricciones y búsqueda, usa Backtracking o B&B.

Modelo general de poda

P o d a = Infactibilidad \cup Suboptimalidad

La poda es la herramienta para combatir la explosión combinatoria. La Infactibilidad elimina lo que es imposible (Backtracking); la Suboptimalidad elimina lo que, aunque sea posible, no vale la pena (Branch and Bound). La unión de ambas maximiza la eficiencia.