Objetivo de dynamic programming: evitar calcular lo mismo varias veces, manteniendo una tabla de los resultados a medida que se calculan, para luego usarlos en la solución de las subinstancias
Divide and conquer es una familia con un sistema top-down, porque vamos de la instancia completa, hasta llegar a subinstancias.
Por otro lado, Dynamic Programming, es bottom-up, se inicia con las subinstancias mas pequeñas y simples, y combinando sus soluciones obtenemos la respuestas de otras mas grandes, hasta dar con la solución final.
1. Describir estructura:
2. Definir el valor
3. Calcular el valor
4. Calcular solución (opcional)
memoización: para top-down, recursivos:
tabulacion para bottom-up, iterativos:
Se utiliza el triángulo de Pascal, como tabla de valores intermedios. No es necesaria toda la tabla: es suficiente con un vector de tamaño k, que es una línea, luego se actualiza el vector de izquierda a derecha.
Coeficiente binomial:
->El problema de coeficiente binomial (n/k) es: tiempo a en 8(n k) y espacio 8(k).
The World Series:
A= p y B =q=1-p.
P(i,j) probabilidad de que el equipo A gane, cuando le faltan i ganes, y a B le faltan j ganes.
P(i,j) = pP(i-1,j)+qP(i,j-1)
->El problema de la serie mundial es t(k) donde k=i+j, O(2^k). O(4^n) si j=i=n.
En términos de coeficiente binomial:
C(i+j,j) = C(i+j-1, j) + C(i+j-1, j-1)
-> Con triangulo de Pascal se puede hacer 8(n^2)
Cambio:
Se hace una tabla donde las filas son las denominaciones disponibles, y las columnas son de 0 a N, valor a pagar. c[i, j] menor numero de monedas para pagar j, con monedas de 1 a i.
Se calcula c[i,0] y después de eso, se puede calcular de derecha a izquierda columna por columna, o de arriba a abajo fila por fila.
c[i, j] = min(c[i-1, j],1+c[i, j-di])
-> 8(n+c[n,N])
Principio de la optimalidad:
en una secuencia optima de decisiones o selecciones, cada subsequencia también debe ser óptima.
O sea, si necesito un resultado optimo, todos los pequeños resultados en el camino(la tabla) deben ser óptimos.
Cuando el principio no aplica, entonces probablemente no se puede usar prog dinámica.
Un problema para el principio es los recursos, puedo agotar los recursos en una subinstancia del problema.
La solución óptima a cualquier instancia no trivial de un problema, es la combinación de optimas soluciones de algunas de sus subinstancias.
Problema de la mochila:
vi y wi son restricciones de la instancia. Y xi (es 1 o 0 si está o no está en la mochila) son restricciones de la solución.
Se hace una tabla, con filas para cada objeto y columnas para su peso. Por eso V[i,j] es la cantidad de objetos que podemos llevar en la mochila de peso j. Con objetos de 1 a i.
v[i,j] = max(V[i-1, j],V[i-1,j-wi]+vi)
-> construir la tabla 8(nW) y la composision se determina en tiempo o(n+W)
Camino más corto:
Dk[i,j] = min(Dk[i,j],Dk-1[i,k]+Dk-1[k,j])
No entendí
Multiplicación matricial en cadena:
La complejidad de una multiplicación de matrices: es pqr. La idea es encontrar la mejor forma de poner paréntesis para que sean menos multiplicaciones.
Supongamos hago un corte de m1 a mi= M= (m1,m2,m3,...mi)(mi+1,mi+2,...mn) ambas deben ser optimas(principio de la optimabilidad).
Recurrencia T(n)= Suma de i=1 hasta n-1 de T(i)T(n-i). Sus valores son llamados números catalanes. -> omega(4^n/n)
-> alg con diagonal, n^3
Ejemplos con recursión:
-Matrices:
Se puede hacer calculando M con una función fm() que sea recursiva. Para saber cuantas multiplicaciones se ocupan se llama a fm(1,n)
-> Toma Omega(2^n), O(3^n)
Funciones de memoria:
Combinar las ventajas de top down y de bottom up. Se hace con una función de memora.
Se tiene la tabla de valores, si ya esa tabla se calculó se retorna el valor correspondiente. Si no, se llama recursivamente a la función.
-> tiempo: 8(nk) y espacio omega(nk)
Características generales:
-Set de candidatos: a tomar en cuenta.
-Set de candidatos considerados: fueron elegidos para la solución.
-Set de candidatos rechazados: fueron rechazados y ya no serán tomados en cuenta.
+Función solución: verifica que los candidatos den una solución al problema.
+Función factibilidad: verifica si los candidatos son factibles para obtener una solución.
+Función de selección: selecciona de los candidatos aún no seleccionados, cuál es el más prometedor.
+Función objetiva: nos da la solución que hemos encontrado. Esta puede no estar explícitamente en el código.
MSTs:
Grafo conexo, pesado y no dirigido.
Debe tener n-1 arcos, n es la cantidad de nodos totales. Esto para que no hayan ciclos.
Kruskal:
Algoritmo para MST, que comienza vacío, y va agregando T resultado.
Agrega de forma creciente según el peso, y no le importa los nodos, solo no formar ciclos.
-> 8(a log n). n nodos y a arcos.
Prim:
Se inicia de una raíz arbitraria, cada paso agrega un nuevo nodo, hasta que todos los nodos se hayan incluído.
-> 8(n^2)
Es mejor usar Prim que Kruskal cuando a>n^2/log n, a es cantidad de arcos
Camino más corto(Dijkstra):
Se selecciona un nodo, y se quiere saber el camino más corto para llegar a todos los otros nodos.
C es nodos candidatos, D es solución (largos).
-> Normal: 8(n^2)
Problema de la mochila:
Se busca llenar una mochila con un peso máximo, con objetos con un peso y un valor, se busca el mayo valor respetando ese peso. Se pueden dividir objetos.
->O(n log n)
Planificación:
Minimizar tiempo en el sistema:
Un solo servicio, como un mae en un banco, procesador, etc. Tiene n clientes que atender, se sabe cuanto va a durar cada cliente. Se quiere minimizar el tiempo promedio de espera.
El caso óptimo es atender primero a los de menor tiempo primero. Sólo es necesario ordenar esos tiempos. Los nuevos que lleguen se acomodan al final y se vuelve a poner en orden creciente.
-> solo es ordenar, O(n log n)
Planificación con tiempos de entrega:
Tenemos trabajos con valor y tiempo. Se elije una secuencia que se pueda hacer en el tiempo indicado y nos de mayor ganancia.
