jueves, 7 de mayo de 2009

Proceso de resolución de problemas de programación dinámica

En general el problema se puede usando un proceso de tres pasos:

  • Separar el problema en subproblemas más pequeños.
  • Resolver estos problemas óptimamente usando este proceso de tres pasos de manera recursiva.
  • Use las soluciones optimas para construir una solución óptima del problema original.
Los subproblemas son así mismo resueltos dividiendo estos en subproblemas y así en adelante hasta que se alcance el caso más simple que sea fácil de resolver.

Decir que un problema tiene subproblemas sobrepuestos es decir que un mismo subproblema es usado para resolver muchos problemas diferentes
más grandes.

Por ejemplo en la secuencia de Fibonacci F3 = F1 + F2 y F4 = F2 + F3, el calculo de cada número involucra el cálculo de F2. Ya que ambos F3 y F4 son necesarios para calcular F5, un método ingenuo para calcular F5 puede terminar haciendo el calculo de F2 dos o más veces.

Cuando los subproblemas se sobreponen un método puede perder tiempo recalculando soluciones óptimas de subproblemas ya resueltos.

A fin de evitar la repetición de cálculos, se pueden guardar las soluciones a los problemas ya resueltos de manera que si se requiere resolver el mismo problema después, se puede reutilizar los cálculos
hechos previamente.

Este approach es llamado memoización (no memorización).

Cuando se este seguro de que una solución particular ya no se necesita más se puede entonces borrarla, liberando así el espacio.

En algunos casos se pueden hacer cómputos que se saben se requerirán en lo posterior.

4 comentarios:

  1. OJOS PARCHADOS POR SIEMPRE

    ResponderEliminar
  2. para poner tremenda basura uno no se toma la molestia de publicar algo, es mejor que aprobeches el tiempo buscando en los contenedores que seguro q encuentras algo mas util!!!

    ResponderEliminar
  3. PUÑAL DE MIERDA HIJO DE PUTA ESTO ES SOLO UN COPYPASTE DE WIKIPEDIA JOTO PUÑETERO.
    VETE A LA VERGA PINCHE PUTO SI VAS A PUBLICAR ALGO PORLO MENOS METELE MAS DETALLE A LO COPIADO PUÑAL.
    TU PUTA MADRE

    ResponderEliminar