Scribd
Cargar
7 vistas2 páginas

Introducción a la Programación Dinámica

La Programación Dinámica es una técnica que mejora la eficiencia de soluciones recursivas a problemas con subproblemas solapados, evitando la repetición de cálculos al almacenar soluciones en una tabla. Se aplica principalmente en problemas de optimización, donde se busca la solución de valor óptimo, y se basa en el principio de óptimo de Bellman. Sin embargo, es importante verificar la aplicabilidad de este principio en cada caso específico.

Cargado por

fmelendezv777
Derechos de autor
© All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como DOCX, PDF, TXT o lee en línea desde Scribd
7 vistas2 páginas

Introducción a la Programación Dinámica

La Programación Dinámica es una técnica que mejora la eficiencia de soluciones recursivas a problemas con subproblemas solapados, evitando la repetición de cálculos al almacenar soluciones en una tabla. Se aplica principalmente en problemas de optimización, donde se busca la solución de valor óptimo, y se basa en el principio de óptimo de Bellman. Sin embargo, es importante verificar la aplicabilidad de este principio en cada caso específico.

Cargado por

fmelendezv777
Derechos de autor
© All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como DOCX, PDF, TXT o lee en línea desde Scribd

PROGRAMACIÓN DINÁMICA

Existe una serie de problemas cuyas soluciones pueden ser expresadas


recursivamente en términos matemáticos, y posiblemente la manera más natural
de resolverlos es mediante un algoritmo recursivo. Sin embargo, el tiempo de
ejecución de la solución recursiva, normalmente de orden exponencial y por tanto
impracticable, puede mejorarse substancialmente mediante la Programación
Dinámica.

En el diseño Divide y Vencerás del capítulo 3 veíamos cómo para resolver un


problema lo dividíamos en subproblemas independientes, los cuales se resolvían de
manera recursiva para combinar finalmente las soluciones y así resolver el
problema original. El inconveniente se presenta cuando los subproblemas obtenidos
no son independientes sino que existe solapamiento entre ellos; entonces es
cuando una solución recursiva no resulta eficiente por la repetición de cálculos que
conlleva. En estos casos es cuando la Programación Dinámica nos puede ofrecer
una solución aceptable. La eficiencia de esta técnica consiste en resolver los
subproblemas una sola vez, guardando sus soluciones en una tabla para su futura
utilización.

La Programación Dinámica no sólo tiene sentido aplicarla por razones de eficiencia,


sino porque además presenta un método capaz de resolver de manera eficiente
problemas cuya solución ha sido abordada por otras técnicas y ha fracasado.

Donde tiene mayor aplicación la Programación Dinámica es en la resolución de


problemas de optimización. En este tipo de problemas se pueden presentar
distintas soluciones, cada una con un valor, y lo que se desea es encontrar la
solución de valor óptimo (máximo o mínimo).

La solución de problemas mediante esta técnica se basa en el llamado principio de


óptimo enunciado por Bellman en 1957 y que dice:

“En una secuencia de decisiones óptima toda sub secuencia ha de ser también
óptima”.

Hemos de observar que aunque este principio parece evidente no siempre es


aplicable y por tanto es necesario verificar que se cumple para el problema en
cuestión. Un ejemplo claro para el que no se verifica este principio aparece al tratar
de encontrar el camino de coste máximo entre dos vértices de un grafo ponderado.
Tecnológico de Estudios Superiores de Coacalco

TESCo

Licenciatura en Informática

ALUMNO:

LIEVANO PEÑA LUIS ROBERTO

GRUPO: 7421

TURNO: VESPERTINO

FECHA DE ENTREGA:

18/JULIO/2011

También podría gustarte