Algoritmos De Programación Dinámica
Páginas: 7 (1632 palabras)
Publicado: 3 de junio de 2012
Algoritmos de Programación Dinámica
Juan Aguilera
juaguile@alumnos.ubiobio.cl
Cesar Urbina
curbina@alumnos.ubiobio.cl
Introducción: this work pretends analyze and design an Dynamic Programming Algorithm, either manually or through Matlab programming.
Palabras Clave: Programación Dinámica, DP, Algoritmo, Brazo Robótico, Optimización, Matlab.Descripción del Problema
En el presente informe se pretende explicar a grandes rasgos lo que es un Algoritmo de Programación Dinámica, así como también dar a conocer dos de los más conocidos. También se propone un sistema que consiste en definir trayectorias para un brazo robótico, en los cuales, ambos algoritmos se aplicarán para comprobar su efectividad en ese tipo de sistemas. Finalmente sepresentarán los resultados obtenidos de la simulación del algoritmo en Matlab, y se compararán con resultados obtenidos manualmente.
Programación Dinámica
En la ingeniería existe una serie de problemas cuyas soluciones pueden ser abordadas de forma recursiva en términos matemáticos, y probablemente la manera más común de resolverlos es mediante un algoritmo recursivo. Sin embargo, su tiempo deejecución, generalmente exponencial y por ende, impracticable, puede perfeccionarse mediante la programación dinámica. La idea principal de esta técnica consiste en dividir el problema en sub-problemas o etapas, y de esta manera abordarlos y resolverlos una sola vez, guardando sus soluciones en una tabla para su futura utilización. Esta técnica no solamente tiene sentido aplicarla por motivos deeficiencia, sino porque posee un método capaz de resolver problemas de manera eficiente, problemas cuya solución ha sido abordada por otras técnicas, y lamentablemente han fracasado. Esta técnica basa su desempeño en tres variables:
k = Etapa
uk = Decisión en cada etapa
xk = Estados
Estados son las situaciones en las que se puede encontrar el sistema en cada etapa.
A través de unadecisión uk se va desde un estado xk al comienzo de una etapa k, a otro estado xk+1 al comienzo de la siguiente etapa k+1, como se presenta en la siguiente figura:
Figura[1]: Decisión entre 2 Etapas.
En cada etapa se evalúa la decisión óptima para cada uno de sus estados xk. Cada estado toda la información necesaria para tomar decisiones futuras sin necesidad de conocer cómo se ha alcanzadodicho estado.
La mayor aplicación de este algoritmo esencialmente es en la resolución de problemas de optimización. En este tipo de problemas pueden presentarse distintas soluciones, y lo que se pretende es encontrar la solución óptima. La solución de este tipo de problemas se basa en lo que se conoce como Principio del Óptimo de Bellman, y que expone: “En una secuencia de decisiones óptima todasub-secuencia ha de ser también óptima”¹.
Para que un problema pueda ser abordado por esta técnica deben cumplirse dos condiciones:
* La solución del problema debe ser alcanzada a través de una secuencia de decisiones, una en cada etapa.
* Dicha secuencia de decisiones debe cumplir el Principio del Óptimo de Bellman.
En resumen, el diseño de un Algoritmo de ProgramaciónDinámica consta de los siguientes pasos:
* Planteamiento de la solución como una sucesión de decisiones y verificación de que se cumple por el Principio del Óptimo.
* Definición recursiva de la solución.
* Cálculo del valor de la solución óptima mediante una tabla en donde se almacenan soluciones a problemas parciales para reutilizar los cálculos.
* Construcción de la soluciónóptima, haciendo uso de la información contenida en la tabla anterior.
A continuación se detallarán dos algoritmos muy conocidos de Programación Dinámica: Barckward DP y Fordward DP, los que sucesivamente se aplicarán a un ejemplo práctico relacionado con la optimización de tramos de un brazo robótico.
Descripción del Sistema
En relación a la aplicación de un Algoritmo DP...
Juan Aguilera
juaguile@alumnos.ubiobio.cl
Cesar Urbina
curbina@alumnos.ubiobio.cl
Introducción: this work pretends analyze and design an Dynamic Programming Algorithm, either manually or through Matlab programming.
Palabras Clave: Programación Dinámica, DP, Algoritmo, Brazo Robótico, Optimización, Matlab.Descripción del Problema
En el presente informe se pretende explicar a grandes rasgos lo que es un Algoritmo de Programación Dinámica, así como también dar a conocer dos de los más conocidos. También se propone un sistema que consiste en definir trayectorias para un brazo robótico, en los cuales, ambos algoritmos se aplicarán para comprobar su efectividad en ese tipo de sistemas. Finalmente sepresentarán los resultados obtenidos de la simulación del algoritmo en Matlab, y se compararán con resultados obtenidos manualmente.
Programación Dinámica
En la ingeniería existe una serie de problemas cuyas soluciones pueden ser abordadas de forma recursiva en términos matemáticos, y probablemente la manera más común de resolverlos es mediante un algoritmo recursivo. Sin embargo, su tiempo deejecución, generalmente exponencial y por ende, impracticable, puede perfeccionarse mediante la programación dinámica. La idea principal de esta técnica consiste en dividir el problema en sub-problemas o etapas, y de esta manera abordarlos y resolverlos una sola vez, guardando sus soluciones en una tabla para su futura utilización. Esta técnica no solamente tiene sentido aplicarla por motivos deeficiencia, sino porque posee un método capaz de resolver problemas de manera eficiente, problemas cuya solución ha sido abordada por otras técnicas, y lamentablemente han fracasado. Esta técnica basa su desempeño en tres variables:
k = Etapa
uk = Decisión en cada etapa
xk = Estados
Estados son las situaciones en las que se puede encontrar el sistema en cada etapa.
A través de unadecisión uk se va desde un estado xk al comienzo de una etapa k, a otro estado xk+1 al comienzo de la siguiente etapa k+1, como se presenta en la siguiente figura:
Figura[1]: Decisión entre 2 Etapas.
En cada etapa se evalúa la decisión óptima para cada uno de sus estados xk. Cada estado toda la información necesaria para tomar decisiones futuras sin necesidad de conocer cómo se ha alcanzadodicho estado.
La mayor aplicación de este algoritmo esencialmente es en la resolución de problemas de optimización. En este tipo de problemas pueden presentarse distintas soluciones, y lo que se pretende es encontrar la solución óptima. La solución de este tipo de problemas se basa en lo que se conoce como Principio del Óptimo de Bellman, y que expone: “En una secuencia de decisiones óptima todasub-secuencia ha de ser también óptima”¹.
Para que un problema pueda ser abordado por esta técnica deben cumplirse dos condiciones:
* La solución del problema debe ser alcanzada a través de una secuencia de decisiones, una en cada etapa.
* Dicha secuencia de decisiones debe cumplir el Principio del Óptimo de Bellman.
En resumen, el diseño de un Algoritmo de ProgramaciónDinámica consta de los siguientes pasos:
* Planteamiento de la solución como una sucesión de decisiones y verificación de que se cumple por el Principio del Óptimo.
* Definición recursiva de la solución.
* Cálculo del valor de la solución óptima mediante una tabla en donde se almacenan soluciones a problemas parciales para reutilizar los cálculos.
* Construcción de la soluciónóptima, haciendo uso de la información contenida en la tabla anterior.
A continuación se detallarán dos algoritmos muy conocidos de Programación Dinámica: Barckward DP y Fordward DP, los que sucesivamente se aplicarán a un ejemplo práctico relacionado con la optimización de tramos de un brazo robótico.
Descripción del Sistema
En relación a la aplicación de un Algoritmo DP...
Leer documento completo
Regístrate para leer el documento completo.