UNIVERSIDAD ESTATAL DEL SUR DE MANABÍ.
FACULTADDECIENCIASTÉCNICAS.
CARRERADETECNOLOGÍADELAINFORMACIÓN.
MATERIA:
Investigación de Operaciones
TEMA:
Modelos de Programación Dinámica
INTEGRANTES DEL GRUPO
Quimis Castro Jonathan Steven
Intriago Garcia Johan Enrique
Choez Garcia Cristopher Alexander
DOCENTE:
Ing. Yanina Holanda Campozano Pilay
Jipijapa-Manabí-Ecuador
Periodo académico PII 2023
PROGRAMACIÓN DINÁMICA
La programación dinámica es una técnica de optimización que se utiliza para resolver
problemas complejos dividiéndolos en subproblemas más pequeños y resolviendo cada
subproblema solo una vez, almacenando sus soluciones para evitar el recalculo. Esta
técnica se utiliza en una variedad de campos, como la informática, la ingeniería, la
economía y la biología (kariuki, 2022).
Existen dos tipos principales de programación dinámica: la determinística y la
probabilística.
1. Programación Dinámica Determinística:
Definición: En la programación dinámica determinística, se asume que las
transiciones entre los estados son completamente conocidas y no hay
incertidumbre asociada con ellas (Anonimo, 2023).
Características:
La solución al problema se basa en la optimización de una función
objetivo, y la naturaleza de las transiciones entre estados es conocida y
fija.
Se utiliza para resolver problemas de optimización donde se busca
encontrar la mejor solución posible bajo ciertas restricciones.
Ejemplos comunes incluyen el problema de la mochila, el algoritmo de
Floyd-Warshall para encontrar caminos más cortos en grafos, y la
secuencia de Fibonacci utilizando memorización.
2. Programación Dinámica Probabilística:
Definición: En la programación dinámica probabilística, se introduce la
incertidumbre en las transiciones entre estados. En lugar de tener transiciones
determinísticas, hay ciertas probabilidades asociadas con los posibles resultados
(Villanueva, 2018).
Características:
Se utiliza en problemas donde las transiciones entre estados no son
completamente predecibles y pueden depender de factores aleatorios o
probabilidades.
Es común en problemas de toma de decisiones bajo incertidumbre, como
en problemas de teoría de juegos o en la planificación probabilística.
Ejemplos incluyen el algoritmo de Viterbi para decodificación de
señales, algoritmos de planificación de caminos para robots en entornos
inciertos y algunos problemas en inteligencia artificial.
Y entre sus modelos tenemos los siguientes ejemplos:
I. Problema de la Mochila (Knapsack Problem):
Contexto: Este problema se asemeja a un viajero que tiene una mochila con
capacidad limitada y debe decidir qué elementos llevar consigo para
maximizar el valor total, considerando que cada elemento tiene un peso y un
valor asociado. Es aplicable en situaciones donde se enfrenta a limitaciones
de recursos y se busca la mejor combinación para optimizar un objetivo,
como la asignación eficiente de recursos limitados (Fernández, 2007).
II. Secuencia Común más Larga (Longest Common Subsequence - LCS):
Contexto: La búsqueda de la secuencia común más larga se utiliza en
problemas relacionados con comparación de cadenas de texto o secuencias,
como la bioinformática para comparar genomas. Se busca identificar la
subsecuencia más larga que es común a dos o más secuencias, siendo útil en
campos donde la similitud entre datos secuenciales es fundamental.
III. Rutas más Cortas (Shortest Paths):
Contexto: La búsqueda de las rutas más cortas es esencial en problemas de
optimización de redes y logística. Algoritmos como Dijkstra y Floyd-
Warshall se aplican para encontrar la ruta más corta entre nodos en un grafo
ponderado, siendo valiosos en la planificación de rutas eficientes en redes de
transporte o comunicación.
IV. Problema del Viajante de Comercio (Traveling Salesman Problem - TSP):
Contexto: Este problema modela la situación en la que un vendedor debe
visitar un conjunto de ciudades y regresar a la ciudad de origen, buscando
minimizar la distancia total recorrida. Se aplica en logística y distribución,
así como en la optimización de rutas para ahorrar tiempo y recursos.
V. Divide y Vencerás con Programación Dinámica:
Contexto: La combinación de divide y vencerás con programación dinámica
se emplea en algoritmos como el de Strassen para multiplicar matrices de
manera eficiente. Este enfoque es crucial en problemas que pueden dividirse
en subproblemas más pequeños y resolverse de manera independiente antes
de combinar las soluciones (Flores, 2023).
VI. Problema de Subconjunto con Suma (Subset Sum):
Contexto: El problema de subconjunto con suma se presenta en situaciones
donde se busca determinar si existe un subconjunto de un conjunto dado de
números cuya suma es igual a un valor objetivo. Este tipo de problema se
encuentra en la optimización de recursos y la toma de decisiones sobre
asignación de presupuestos.
VII. Problema del Emparejamiento de Paréntesis (Parenthesis Matching):
Contexto: En el ámbito de la verificación de expresiones matemáticas o de
programación, el emparejamiento de paréntesis es crucial para garantizar la
validez sintáctica. Este problema de validación se aplica en la interpretación
de lenguajes de programación y el análisis de estructuras de datos anidadas.
VIII. Optimización de Corte de Palabras (Word Break Problem):
Contexto: En la optimización de corte de palabras, se busca determinar si
una cadena de texto puede ser segmentada en palabras de un diccionario
dado. Este problema es relevante en el procesamiento del lenguaje natural y
la correcta interpretación de cadenas de texto en aplicaciones como
correctores ortográficos y motores de búsqueda.
BIBLIOGRAFÍA
Anonimo. (2023). slideplayer. Obtenido de [Link]
Fernández, S. F. (9 de octubre de 2007). slideshare. Obtenido de
[Link]
Flores, I. (2023). ingenieria. Obtenido de
[Link]
Sesion6_IdaliaFlores_20abr15.pdf
kariuki, c. (2022). geekflare. Obtenido de [Link]
Villanueva, M. M. (2018). slideplayer. Obtenido de [Link]
