Dividir y venceras
Páginas: 9 (2068 palabras)
Publicado: 6 de abril de 2011
6.1. Introducción 139
6.2. Estructura conceptual del capítulo 139
6.3. Dividir y Conquistar, Algoritmos Voraces tienen debilidades? 140
6.4. Definición de Programación Dinámica 140
6.5. Características de la Programación Dinámica 141
6.6. Análisis comparativo de Dividir y Conquistar Versus Programación Dinámica. 142
6.7. Principio de Optimalidad 142
6.8. Resolución deproblemas aplicando Programación Dinámica 143
6.8.1. Problema de la ruta más corta 143
6.8.2. Cálculo del Coeficiente Binomial 144
6.8.3. Edición de sartas de caracteres 147
6.8.4. Problema del morral 148
6.8.5. Problema de apuestas en la Serie Mundial de Béisbol 150
6.9. Bibliografía 153
6.10. Direcciones en Internet 154
6 PROGRAMACIÓN DINÁMICA
6.1. IntroducciónEn el capítulo cuatro se desarrollaron los conceptos relacionados con la técnica de Dividir y Conquistar, de una forma equivalente la teoría conceptual de soporte a los Algoritmos Voraces se construyo en el capítulo cinco; la solución de un problema tratable computacionalmente mediante las técnicas desarrolladas anteriormente induce varios interrogantes : Qué características debe tener elproblema para ser solucionado por dichas técnicas?, Cuáles son las fortalezas o debilidades de las técnicas ?, Qué tipo de soluciones son proporcionadas por las técnicas ?, Si hay debilidades, qué otra técnicas podemos emplear para la solución del problema ?. Estos interrogantes, son los que pretende responder el presente capítulo.
6.2. Estructura conceptual del capítulo
El capítulo deProgramación Dinámica, desarrolla los siguientes contenidos :
Análisis de debilidades de las técnicas de Dividir y Conquistar y Algoritmos voraces.
Definición de Programación Dinámica.
Características de la Programación Dinámica.
Análisis comparativo de las técnicas Dividir y Conquistar y Programación Dinámica, y
Resolución de problemas tratables computacionalmente aplicando Programación Dinámica.6.3. Dividir y Conquistar, Algoritmos Voraces tienen debilidades?
Las técnicas de Dividir y Conquistar y Algoritmos Voraces, si bien es cierto se constituyen en estrategias para solucionar problemas tratables computacionalmente, presentan algunas fallas cuando se busca la solución de un problema en términos de eficacia y eficiencia en tiempo y espacio.
En el caso de Dividir y Conquistar,como método de refinamiento progresivo el problema central se divide en subproblemas ( los cuales a su vez, se subdividen ), para al final, combinar las soluciones de los subproblemas y así obtener la solución de problema central; esta técnica tiene los siguientes problemas :
Solapamiento de subproblemas, lo cual conlleva a resolver un mismo subproblema dos o más veces para la obtención de lasolución.
Identidad de subproblemas, derivado de la consideración de independencia de subproblemas, lo cual genera subproblemas idénticos y consecuentemente, la duplicidad de dichos aumenta el tiempo y espacio del algoritmo.
La técnica al ser de refinamiento progresivo, va de lo general a lo particular o lo que es equivalente de lo complejo a lo simple, lo cual indica que el problema central ( Pc), se subdivide en subproblemas menores y encontrar sus soluciones para luego ser combinadas; ello implica que es una técnica descendente, y hay problemas computacionales que no permiten ser modelados por ésta técnica.
Por su parte, la técnicas voraces se caracterizan por las siguientes debilidades :
Son limitadas, en el sentido que hay algoritmos que funciona para un número limitado decasos; en éste sentido dan soluciones “aceptables” solamente.
No dan soluciones optímales, al dar soluciones aceptables el algoritmo puede no hallar soluciones optímales.
Por lo tanto, la técnica de Programación Dinámica se presenta como aquella que permite solucionar “en parte” los problemas y debilidades de las técnicas antes mencionadas.
6.4. Definición de Programación Dinámica
La...
6.2. Estructura conceptual del capítulo 139
6.3. Dividir y Conquistar, Algoritmos Voraces tienen debilidades? 140
6.4. Definición de Programación Dinámica 140
6.5. Características de la Programación Dinámica 141
6.6. Análisis comparativo de Dividir y Conquistar Versus Programación Dinámica. 142
6.7. Principio de Optimalidad 142
6.8. Resolución deproblemas aplicando Programación Dinámica 143
6.8.1. Problema de la ruta más corta 143
6.8.2. Cálculo del Coeficiente Binomial 144
6.8.3. Edición de sartas de caracteres 147
6.8.4. Problema del morral 148
6.8.5. Problema de apuestas en la Serie Mundial de Béisbol 150
6.9. Bibliografía 153
6.10. Direcciones en Internet 154
6 PROGRAMACIÓN DINÁMICA
6.1. IntroducciónEn el capítulo cuatro se desarrollaron los conceptos relacionados con la técnica de Dividir y Conquistar, de una forma equivalente la teoría conceptual de soporte a los Algoritmos Voraces se construyo en el capítulo cinco; la solución de un problema tratable computacionalmente mediante las técnicas desarrolladas anteriormente induce varios interrogantes : Qué características debe tener elproblema para ser solucionado por dichas técnicas?, Cuáles son las fortalezas o debilidades de las técnicas ?, Qué tipo de soluciones son proporcionadas por las técnicas ?, Si hay debilidades, qué otra técnicas podemos emplear para la solución del problema ?. Estos interrogantes, son los que pretende responder el presente capítulo.
6.2. Estructura conceptual del capítulo
El capítulo deProgramación Dinámica, desarrolla los siguientes contenidos :
Análisis de debilidades de las técnicas de Dividir y Conquistar y Algoritmos voraces.
Definición de Programación Dinámica.
Características de la Programación Dinámica.
Análisis comparativo de las técnicas Dividir y Conquistar y Programación Dinámica, y
Resolución de problemas tratables computacionalmente aplicando Programación Dinámica.6.3. Dividir y Conquistar, Algoritmos Voraces tienen debilidades?
Las técnicas de Dividir y Conquistar y Algoritmos Voraces, si bien es cierto se constituyen en estrategias para solucionar problemas tratables computacionalmente, presentan algunas fallas cuando se busca la solución de un problema en términos de eficacia y eficiencia en tiempo y espacio.
En el caso de Dividir y Conquistar,como método de refinamiento progresivo el problema central se divide en subproblemas ( los cuales a su vez, se subdividen ), para al final, combinar las soluciones de los subproblemas y así obtener la solución de problema central; esta técnica tiene los siguientes problemas :
Solapamiento de subproblemas, lo cual conlleva a resolver un mismo subproblema dos o más veces para la obtención de lasolución.
Identidad de subproblemas, derivado de la consideración de independencia de subproblemas, lo cual genera subproblemas idénticos y consecuentemente, la duplicidad de dichos aumenta el tiempo y espacio del algoritmo.
La técnica al ser de refinamiento progresivo, va de lo general a lo particular o lo que es equivalente de lo complejo a lo simple, lo cual indica que el problema central ( Pc), se subdivide en subproblemas menores y encontrar sus soluciones para luego ser combinadas; ello implica que es una técnica descendente, y hay problemas computacionales que no permiten ser modelados por ésta técnica.
Por su parte, la técnicas voraces se caracterizan por las siguientes debilidades :
Son limitadas, en el sentido que hay algoritmos que funciona para un número limitado decasos; en éste sentido dan soluciones “aceptables” solamente.
No dan soluciones optímales, al dar soluciones aceptables el algoritmo puede no hallar soluciones optímales.
Por lo tanto, la técnica de Programación Dinámica se presenta como aquella que permite solucionar “en parte” los problemas y debilidades de las técnicas antes mencionadas.
6.4. Definición de Programación Dinámica
La...
Leer documento completo
Regístrate para leer el documento completo.