Programación dinámica

Por ejemplo, el camino más corto entre dos vértices de un grafo se puede encontrar calculando primero el camino más corto al objetivo desde todos los vértices adyacentes al de partida, y después usando estas soluciones para elegir el mejor camino de todos ellos.Esto sucede siempre que haya subproblemas superpuestos: una mala implementación puede acabar desperdiciando tiempo recalculando las soluciones óptimas a problemas que ya han sido resueltos anteriormente.Esto se puede evitar guardando las soluciones que ya hemos calculado.Si estamos seguros de que no volveremos a necesitar una solución en concreto, la podemos descartar para ahorrar espacio.El término también lo usó en los años 40 Richard Bellman, un matemático estadounidense, para describir el proceso de resolución de problemas donde hace falta calcular la mejor solución consecutivamente.Bellman decidió emplear la palabra dinámica a esta técnica, ya que deseaba analizar las variables de los problemas con respecto al tiempo.Siendo así Dasgupta, Papadimitriou y Vazirani (2006), entendieron a la programación dinámica como “optimización de procesos con etapa múltiples”.Es por ello, que se define a la programación dinámica como una técnica matemática que ayuda a resolver decisiones secuenciales interrelacionadas, combinándolas para obtener de la solución óptima.El procedimiento de resolución de la programación dinámica está diseñado para encontrar una política óptima para cada etapa logrando así la política óptima general.1) Programación Dinámica Determinística: El enfoque determinístico consiste en que el estado de la siguiente etapa se encuentra determinado por completo con respecto al estado y la decisión que posee la etapa actual.Al tomar la decisión xn se mueve a algún estado Sn+1 en la etapa n+1.La política de decisión también hace una contribución a la función objetivo.Al combinar estas dos cantidades en la forma apropiada se proporciona a la función objetivo fn(Sn,xn) la contribución de la etapa n en adelante.2) Programación Dinámica Probabilística: En este enfoque, el valor del estado de la siguiente etapa y política de decisión queda completamente determinado mediante una distribución probabilística.En este caso, existe una distribución de probabilidad para determinar cuál será el estado en la siguiente etapa.Si, dada una subsecuencia de decisiones, siempre se conoce cuál es la decisión que debe tomarse a continuación para obtener la secuencia óptima, el problema es elemental y se resuelve trivialmente tomando una decisión detrás de otra, lo que se conoce como estrategia voraz.La programación dinámica se aplica cuando la subdivisión de un problema conduce a: Esta sucesión puede expresarse mediante la siguiente recurrencia:En ejemplos mayores, se recalculan muchos otros valores de fib, o subproblemas.Para evitar este inconveniente, podemos resolver el problema mediante programación dinámica, y en particular, utilizando el enfoque de memoización (guardar los valores que ya han sido calculados para utilizarlos posteriormente).La tabla resultante sería una tabla unidimensional con los resultados desde 0 hasta n. Un programa que calculase esto, usando Bottom-up, tendría la siguiente estructura: La función resultante tiene complejidad O(n), en lugar de 2 a la n (puesto que genera un árbol binario en memoria, donde el último nivel de hojas es de la forma 2 a la n).En otras palabras, la programación dinámica, en este caso, permite disminuir la complejidad computacional del algoritmo.El mismo problema usando Top-down tendría la siguiente estructura: Suponemos que la tabla se introduce por primera vez correctamente inicializada, con todas las posiciones con un valor inválido, como por ejemplo -1, que se distingue por no ser uno de los valores que computa la función.La idea recursiva es que el coste se calcula de la siguiente manera: C(i, j) = T[i, k] + C(k, j) A partir de esta idea, podemos elaborar una expresión recurrente para la solución: Un algoritmo que resuelve este problema es el siguiente, donde T es la matriz de tarifas, origen y destino los embarcaderos del que se parte y al que se llega respectivamente, y C la matriz en la que almacenaremos los resultados de los costes.La función MenorDeLosCandidatos devuelve el menor coste entre dos puntos, utilizando como base la recurrencia anteriormente expuesta.