Siguiente:El Problema de la Mochila Arriba:Tutorial Anterior:Segundo Ejemplo

Características Comunes

Hay un conjunto de características que son comunes a estos dos ejemplos y a todos los problemas de programación dinámica.
  1. El problema se puede dividir en niveles, se requiere una decisión en cada nivel.

    2. En el problema de inversión de capital los niveles fueron las asignaciones para cada planta, la decisión fue cuánto gastar. En el problema de la ruta más corta, los niveles se definieron siguiendo la estructura del grafo, la decisión fue ir al siguiente.
     
  2. Cada nivel tiene un conjunto de estados asociados a él. .

    3. Los estados para el problema de asignación de capital corresponden a la cantidad gastada en ese punto en ese instante de tiempo. Los estados de la ruta más corta fueron los nodos visitados.
     
  3. La decisión en un nivel transfoma un estado en un estado en el siguiente nivel.

    4. En asignación de capital : la decisión de cuánto gastar dado una cantidad total gastada en el siguiente nivel.
    En la ruta más corta: la decisión de donde seguir dado la llegada en el siguiente nivel.
     
  4.  Dado el estado actual, la decisión óptima para cada uno de los estados que faltan no depende de los estados o de decisiones previas.

    5. En asignación de capital : no es necesario conocer cómo se gastó el dinero en los niveles previos, sólo cuánto se gastó.
    En la ruta más corta: no fue necesario conocer cómo se llegó al nodo, sólo se necesitaba saber que se llegó a ese nodo.
     
  5.  Hay una relación de recursividad que identifica la decisión óptima para el nivel j, dado que el nivel j+1 ya fue resuelto.
  6.  El nivel final debe resolverse por si mismo.
Las dos últimas propiedades obedecen a las relaciones de recursividad dadas anteriormente.

La potencialidad de la programación dinámica, y el arte involucrado, es tomar un problema y determinar sus niveles y estados, tal que las características mencionadas se cumplan. Si esto es posible, entonces la relación de recursividad permite encontrar los valores en una forma relativamente fácil. La dificultad está en la determinación de los niveles y de los estados, para visualizar este aspecto se recomienda estudiar y analizar los siguientes ejemplos. 


Siguiente:El Problema de la Mochila Arriba:Tutorial Anterior:Segundo Ejemplo