algoritmos de planificación y programación dinámica para problemas de optimización

Vista previa del material en texto

Algoritmos Computacionales Grupo C 
M. Cruz Apuntes de prueba de regularización Curso de invierno 2022 
algoritmos de planificación y programación dinámica 
para problemas de optimización 
Los algoritmos de planificación y programación 
dinámica son una clase de algoritmos que se utilizan 
para resolver problemas de optimización. Estos 
algoritmos funcionan descomponiendo el problema en 
subproblemas más pequeños y resolviendo estos 
subproblemas de manera recursiva. 
¿Qué son los algoritmos de planificación y 
programación dinámica? 
Los algoritmos de planificación y programación 
dinámica son algoritmos que se basan en el principio de 
optimización por etapas. Este principio consiste en 
dividir el problema en un conjunto de subproblemas 
más pequeños y resolver estos subproblemas de 
manera recursiva. 
¿Cómo funcionan los algoritmos de planificación y 
programación dinámica? 
Los algoritmos de planificación y programación 
dinámica funcionan de la siguiente manera: 
1. Descomponer el problema en subproblemas más 
pequeños: El primer paso es descomponer el 
problema en un conjunto de subproblemas más 
pequeños. 
2. Resolver los subproblemas: Cada subproblema 
se resuelve de manera recursiva utilizando la 
solución de los subproblemas más pequeños. 
3. Combinar las soluciones de los 
subproblemas: Una vez que se han resuelto 
todos los subproblemas, se combinan sus 
soluciones para obtener la solución del problema 
original. 
Ejemplo: 
Un ejemplo de un problema que se puede resolver con 
un algoritmo de planificación y programación dinámica 
es el problema del viajante de comercio. En este 
problema, se trata de encontrar el camino más corto 
que visita todas las ciudades de un conjunto dado. 
Para resolver este 
problema con un 
algoritmo de 
planificación y 
programación dinámica, 
se puede descomponer 
el problema en un 
conjunto de 
subproblemas, cada uno 
de los cuales consiste 
en encontrar el camino 
más corto que visita un 
subconjunto de las 
ciudades. Cada 
subproblema se 
resuelve de manera 
recursiva utilizando la 
solución de los 
subproblemas más 
pequeños. 
Ventajas y desventajas 
de los algoritmos de 
planificación y 
programación dinámica 
Los algoritmos de 
planificación y 
programación dinámica 
tienen una serie de 
ventajas, entre ellas: 
• Pueden resolver 
problemas que 
serían difíciles o 
imposibles de 
resolver con otros 
métodos. 
• Son eficientes en 
términos 
computacionales. 
Sin embargo, los 
algoritmos de 
Algoritmos Computacionales Grupo C 
M. Cruz Apuntes de prueba de regularización Curso de invierno 2022 
planificación y programación dinámica también tienen 
algunas desventajas, entre ellas: 
• Pueden ser difíciles de implementar. 
• Pueden no ser adecuados para problemas con 
un número grande de subproblemas. 
Conclusión 
Los algoritmos de planificación y programación 
dinámica son una herramienta poderosa que se puede 
utilizar para resolver una amplia gama de problemas de 
optimización. Son una buena opción para problemas 
que serían difíciles o imposibles de resolver con otros 
métodos. 
Ideas principales para estudiantes de universidad 
• Los algoritmos de planificación y programación 
dinámica son algoritmos que se basan en el 
principio de optimización por etapas. 
• Los algoritmos de planificación y programación 
dinámica funcionan descomponiendo el 
problema en subproblemas más pequeños y 
resolviendo estos subproblemas de manera 
recursiva. 
• Los algoritmos de planificación y programación 
dinámica tienen una serie de ventajas y 
desventajas. 
Recomendaciones para estudiantes de universidad 
• Para aprender más sobre algoritmos de 
planificación y programación dinámica, se 
recomienda que los estudiantes de universidad 
consulten libros y artículos de investigación 
sobre el tema. 
• Los estudiantes de universidad también pueden 
encontrar recursos útiles en línea, como 
tutoriales y cursos. 
• Practicar con ejemplos de algoritmos de 
planificación y programación dinámica es una 
excelente manera de aprender cómo funcionan 
estos algoritmos. 
Adiciones específicas 
para estudiantes de 
universidad 
• Los estudiantes 
de universidad 
pueden encontrar 
útil aprender 
sobre los 
diferentes tipos 
de algoritmos de 
planificación y 
programación 
dinámica, como 
los algoritmos de 
programación 
dinámica 
adelante-hacia 
atrás y los 
algoritmos de 
programación 
dinámica 
adelante-hacia 
delante. 
• Los estudiantes 
de universidad 
también pueden 
encontrar útil 
aprender sobre 
las diferentes 
aplicaciones de 
los algoritmos de 
planificación y 
programación 
dinámica, como 
la planificación de 
recursos, la 
asignación de 
tareas y la 
gestión de 
inventarios.