Estrategias de diseño

La estrategia consiste en partir el problema en subproblemas del mismo tipo pero más pequeños, resolverlos por separado (normalmente de forma recursiva) y combinar sus soluciones en la del problema original. Se detiene al llegar a un caso tan pequeño que se resuelve directamente, llamado caso base o caso trivial.

Es un enfoque descendente o top-down: se parte del problema completo y se va bajando. Mergesort, quicksort y la búsqueda binaria son sus ejemplos canónicos, y de ahí sale su rasgo típico: partir el problema por la mitad repetidamente introduce un factor logarítmico en la complejidad.

Divide y vencerás exige que los subproblemas sean independientes entre sí. Cuando los subproblemas se solapan y se repiten, la estrategia correcta ya no es esta sino la programación dinámica.

Un algoritmo voraz (greedy) construye la solución paso a paso tomando en cada momento la opción que parece mejor localmente, sin mirar hacia adelante y sin volver atrás a revisar lo decidido. Es la estrategia más rápida y la más simple de programar.

funcion voraz(candidatos):
    solucion = vacio
    mientras la solucion no este completa y queden candidatos:
        c = mejor(candidatos)          // la decisión se toma aquí
        quitar c de candidatos
        si esFactible(solucion + c):   // y no se revisa nunca más
            solucion = solucion + c
    devolver solucion

Su límite es que no siempre llega al óptimo global: una buena decisión local puede cerrar el camino a una solución mejor. Solo se garantiza el óptimo en problemas con la estructura adecuada, y ahí están sus casos de éxito clásicos: Dijkstra, Prim y Kruskal son voraces y sí alcanzan el óptimo.

La programación dinámica ataca problemas cuyos subproblemas se repiten una y otra vez. La idea es no calcular dos veces lo mismo: se guarda el resultado de cada subproblema y se reutiliza cuando vuelve a hacer falta. Con eso, cálculos que por fuerza bruta serían exponenciales bajan a tiempo polinómico.

Tiene dos formas de organizarse. La ascendente o bottom-up empieza por los subproblemas más pequeños y va rellenando una tabla hasta llegar al grande. La descendente o top-down parte del problema completo, baja recursivamente y guarda por el camino lo que va calculando: esa caché de resultados parciales es la memoización.

// Sin memoización: cada llamada vuelve a calcular lo mismo -> exponencial.
funcion fib(n):
    si n <= 1: devolver n
    devolver fib(n - 1) + fib(n - 2)

// Con memoización: cada subproblema se calcula una sola vez -> O(n).
memo = { }
funcion fibMemo(n):
    si n <= 1: devolver n
    si n esta en memo: devolver memo[n]
    memo[n] = fibMemo(n - 1) + fibMemo(n - 2)
    devolver memo[n]

La programación dinámica cambia tiempo por memoria: gasta espacio en guardar resultados parciales para no repetir cálculos. Divide y vencerás no los guarda porque sus subproblemas no se repiten.

La vuelta atrás explora sistemáticamente el árbol de todas las soluciones posibles. Va construyendo una solución parcial y, en cuanto detecta que por ese camino no puede salir nada válido, deshace la última decisión y prueba la siguiente alternativa. De ahí el nombre.

Es una búsqueda exhaustiva, así que encuentra la solución si existe, pero su coste crece muy deprisa: en el peor caso recorre el árbol entero, con complejidad exponencial. Los casos típicos son los sudokus, los laberintos, el problema de las ocho reinas y la coloración de mapas.

Ramificación y poda es la vuelta atrás afinada. Ramificar es abrir las alternativas de cada decisión, igual que antes. Lo nuevo es la poda: antes de bajar por una rama se estima su mejor resultado posible, y si esa estimación ya es peor que la mejor solución encontrada hasta el momento, la rama se descarta entera sin explorarla.

El resultado es el mismo óptimo que daría la búsqueda exhaustiva, pero visitando muchos menos nodos. En el peor caso sigue siendo exponencial, porque la poda no garantiza recortar nada: si ninguna estimación permite descartar, se explora todo.

La vuelta atrás retrocede cuando comprueba que el camino no es válido; ramificación y poda descarta ramas antes de recorrerlas, usando cotas y resultados ya obtenidos.

Un algoritmo probabilístico o aleatorizado toma alguna decisión al azar durante su ejecución, de modo que dos ejecuciones sobre los mismos datos no tienen por qué comportarse igual. Se recurre a ellos cuando la solución exacta es demasiado cara y basta con una respuesta buena en un tiempo razonable.

Montecarlo arriesga el resultado para controlar el tiempo; Las Vegas arriesga el tiempo para asegurar el resultado.