programacion dinamica
Páginas: 3 (576 palabras)
Publicado: 10 de marzo de 2015
La programación dinámica. Concepto
Frecuentemente para resolver un problema complejo se tiende a dividir este en subproblemas, más pequeños, resolver estos últimos (recurriendo posiblemente a nuevassubdivisiones) y combinar las soluciones obtenidas para calcular la solución del problema inicial. Puede ocurrir que la división natural del problema conduzca a un gran número de subejemplaresidénticos. Si se resuelve cada uno de ellos sin tener en cuenta las posibles repeticiones, resulta un algoritmo ineficiente; en cambio si se resuelve cada ejemplar distinto una sola vez y se conserva elresultado, el algoritmo obtenido es mucho mejor.
Esta es la idea de la programación dinámica: no calcular dos veces lo mismo y utilizar normalmente una tabla de resultados que se va rellenando a medidaque se resuelven los subejemplares.
La programación dinámica es un método ascendente. Se resuelven primero los subejemplares más pequeños y por tanto más simples. Combinando las soluciones se obtienenlas soluciones de ejemplares sucesivamente más grandes hasta llegar al ejemplar original.
Ejemplo:
Consideremos el cálculo de números combinatorios. El algoritmo sería:
funcion C(n, k) si k=0 o k=n entonces devolver 1
si no devolver C(n-1, k-1) + C(n-1, k)
Ocurre que muchos valores C(i, j), con i
La programación dinámica se emplea a menudo para resolver problemas de optimización que satisfacen el principio de optimalidad: en una secuencia óptima de decisiones todasubsecuencia ha de ser también óptima.
VENDEDOR VIAJERO.
Este es la problemática más cotidiana y más complicada de solucionar dentro de los problemas logísticos para cualquier empresa. ¿Cual es lamanera optima para repartir o recorrer ciertos lugares de la manera más rápida y menos costosa? Esta problemática pertenece a la categoría de NP - Completo, por ende, no posee una solución...
Frecuentemente para resolver un problema complejo se tiende a dividir este en subproblemas, más pequeños, resolver estos últimos (recurriendo posiblemente a nuevassubdivisiones) y combinar las soluciones obtenidas para calcular la solución del problema inicial. Puede ocurrir que la división natural del problema conduzca a un gran número de subejemplaresidénticos. Si se resuelve cada uno de ellos sin tener en cuenta las posibles repeticiones, resulta un algoritmo ineficiente; en cambio si se resuelve cada ejemplar distinto una sola vez y se conserva elresultado, el algoritmo obtenido es mucho mejor.
Esta es la idea de la programación dinámica: no calcular dos veces lo mismo y utilizar normalmente una tabla de resultados que se va rellenando a medidaque se resuelven los subejemplares.
La programación dinámica es un método ascendente. Se resuelven primero los subejemplares más pequeños y por tanto más simples. Combinando las soluciones se obtienenlas soluciones de ejemplares sucesivamente más grandes hasta llegar al ejemplar original.
Ejemplo:
Consideremos el cálculo de números combinatorios. El algoritmo sería:
funcion C(n, k) si k=0 o k=n entonces devolver 1
si no devolver C(n-1, k-1) + C(n-1, k)
Ocurre que muchos valores C(i, j), con i
La programación dinámica se emplea a menudo para resolver problemas de optimización que satisfacen el principio de optimalidad: en una secuencia óptima de decisiones todasubsecuencia ha de ser también óptima.
VENDEDOR VIAJERO.
Este es la problemática más cotidiana y más complicada de solucionar dentro de los problemas logísticos para cualquier empresa. ¿Cual es lamanera optima para repartir o recorrer ciertos lugares de la manera más rápida y menos costosa? Esta problemática pertenece a la categoría de NP - Completo, por ende, no posee una solución...
Leer documento completo
Regístrate para leer el documento completo.