Page 93 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

Programación dinámica (dynamic programming)

INtroduccIóN

Con la estrategia del avaro o codicioso se intenta buscar en forma local el siguiente punto para me-
jorar la función (maximizar la ganancia o minimizar el costo). La técnica de la programación dinámica
busca un óptimo global; su estrategia es localizar todos los subóptimos de un grafo dado.

prINcIpIo de optIMalIdad de BellMaN

Cuando hablamos de optimizar nos referimos a buscar la mejor solución (pueden ser varias) de entre
muchas alternativas posibles. Este proceso de optimización puede ser visto como una secuencia
de decisiones que nos proporcionan la solución correcta. Si dada una subsecuencia de decisiones
siempre se conoce cuál es la decisión que debe tomarse a continuación para obtener la secuencia
óptima, el problema es elemental y se resuelve trivialmente tomando una decisión detrás de otra, lo
que se conoce como estrategia voraz. En otros casos, aunque no sea posible aplicar la estrategia
voraz, puede cumplirse el principio de optimalidad de Bellman enunciado en 1957, el cual señal que
“dada una secuencia óptima de decisiones, toda subsecuencia de ella es, a su vez, óptima”.

En este caso, sigue siendo posible ir tomando decisiones elementales, pues se confía que la combi-
nación de ellas seguirá siendo óptima, aunque será necesario explorar muchas secuencias de deci-
siones para dar con la correcta, punto en el cual interviene la programación dinámica. Aunque este
principio parece evidente, no siempre es aplicable y, por tanto, es necesario verificar que se cumpla
para el problema en cuestión.

Contemplar un problema como una secuencia de decisiones equivale a dividirlo en problemas más
pequeños y, en consecuencia, más fáciles de resolver como hacemos en divide y vencerás, técnica
similar a la de programación dinámica, la cual se aplica cuando la subdivisión de un problema con-
duce a lo siguiente:

• Una enorme cantidad de problemas.

• Problemas cuyas soluciones parciales se solapan.

• Grupos de problemas de muy distinta complejidad.

Para que un problema pueda ser abordado por esta técnica debe cumplir dos
condiciones:

87