Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 45 vistas

    Tarea 3 Opt PDF

    Cargado por

    erick
    Este documento describe la naturaleza recursiva de los cálculos de programación dinámica. Explica que la programación dinámica descompone un problema en subproblemas más pequeños, y que la solución de cada subproblema se usa como entrada para el siguiente subproblema, llegando a una solución para el problema completo al resolver el último subproblema. También describe el principio de optimalidad de la programación dinámica y cómo puede implementarse la recursividad hacia adelante o hacia atrás.

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd

    Tarea 3 Opt PDF

    Cargado por

    erick
    45 vistas3 páginas
    Este documento describe la naturaleza recursiva de los cálculos de programación dinámica. Explica que la programación dinámica descompone un problema en subproblemas más pequeños, y que la solución de cada subproblema se usa como entrada para el siguiente subproblema, llegando a una solución para el problema completo al resolver el último subproblema. También describe el principio de optimalidad de la programación dinámica y cómo puede implementarse la recursividad hacia adelante o hacia atrás.

    Título original

    Tarea 3 Opt..pdf

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

    PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    Este documento describe la naturaleza recursiva de los cálculos de programación dinámica. Explica que la programación dinámica descompone un problema en subproblemas más pequeños, y que la solución de cada subproblema se usa como entrada para el siguiente subproblema, llegando a una solución para el problema completo al resolver el último subproblema. También describe el principio de optimalidad de la programación dinámica y cómo puede implementarse la recursividad hacia adelante o hacia atrás.

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    45 vistas3 páginas

    Tarea 3 Opt PDF

    Cargado por

    erick
    Este documento describe la naturaleza recursiva de los cálculos de programación dinámica. Explica que la programación dinámica descompone un problema en subproblemas más pequeños, y que la solución de cada subproblema se usa como entrada para el siguiente subproblema, llegando a una solución para el problema completo al resolver el último subproblema. También describe el principio de optimalidad de la programación dinámica y cómo puede implementarse la recursividad hacia adelante o hacia atrás.

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    de 3

    Alumno: Eduardo Garcia Lobaton.

    Docente: Ing. Francisco Gerardo


    Suárez Beltrán.

    Materia: Optimización II

    Tarea 3

    San Luis Potosí, S.L.P. a 03 de Agosto


    de 2020.
    NATURALEZA RECURSIVA DE LOS CÁLCULOS DE PROGRAMACIÓN
    DINÁMICA (PD) .
    La idea principal de la programación dinámica (PD) es descomponer el problema en
    subproblemas (más manejables). Los cálculos se realizan entonces recursivamente
    donde la solución óptima de un subproblema se utiliza como dato de entrada al
    siguiente problema. La solución para todo el problema está disponible cuando se
    soluciona el último subproblema. La forma en que se realizan los cálculos recursivos
    depende de cómo se descomponga el problema original. En particular, normalmente
    los subproblemas están vinculados por restricciones comunes. La factibilidad de
    estas restricciones comunes se mantiene en todas las iteraciones.
    Ecuación recursiva.
    Esta sección muestra cómo pueden expresarse matemáticamente los cálculos
    recursivos en el ejemplo 12.1-1. Sea fi(xi) la distancia más corta al nodo xi en la
    etapa i, y defina d(xi21, xi) como la distancia del nodo xi21 al nodo xi. La ecuación
    recursiva de PD se define como Todas las distancias se miden desde 0 al
    establecer f0(x0 = 1) = 0. La ecuación recursiva principal expresa la distancia más
    corta fi(xi) en la etapa i como una función del siguiente nodo, xi. En terminología de
    PD, xi se conoce como el estado en la etapa i. El estado conecta las etapas
    sucesivas de una manera que permite tomar decisiones factibles óptimas en una
    etapa futura independientemente de las decisiones que se hayan tomado en todas
    las etapas precedentes. La definición del estado conduce al siguiente marco
    unificador para la PD.
    Principio de optimalidad.
    Las decisiones futuras para todas las etapas futuras constituyen una política óptima
    independientemente de la política adoptada en todas las etapas precedentes. La
    implementación del principio de optimalidad es evidente en los cálculos del ejemplo
    12.1-1. En la etapa 3, los cálculos recursivos en el nodo 7 utilizan la distancia más
    corta a los nodos 5 y 6 (es decir, los estados de la etapa 2) sin preocuparse sobre
    cómo se llega a los nodos 5 y 6 desde el nodo de inicio 1. El principio de optimalidad
    no aborda los detalles de cómo se optimiza un subproblema. La razón es la
    naturaleza genérica del subproblema. Puede ser lineal o no lineal, y la cantidad de
    alternativas puede ser finita o infinita.Todo lo que hace el principio de optimalidad es
    “descomponer” el problema original en subproblemas más manejables
    computacionalmente
    12.2 RECURSIVIDAD HACIA ADELANTE (AVANCE) Y HACIA ATRÁS
    (RETROCESO)
    Naturalmente, la recursividad hacia adelante y hacia atrás da la misma solución
    óptima. Aun cuando el procedimiento hacia adelante parece más lógico, la mayor
    parte de la literatura de PD utiliza la recursividad hacia atrás. La razón de esta
    preferencia es que, por lo general, la recursividad hacia atrás puede ser más
    eficiente desde el punto de vista computacional.
    Recursividad:
    La recursividad, también llamada recursión o recurrencia, es la forma en la cual se
    especifica un proceso basado en su propia definición. O sea, si se tiene un problema de
    tamaño N, este puede ser dividido en instancias más pequeñas que N del mismo
    problema y conociendo la solución de las instancias más simples, se puede aplicar
    inducción a partir de estas asumiendo que quedan resueltas.

    Bibliografía:
    https://www.ecured.cu/Recursividad

    También podría gustarte