Esta es una optimización para calcular los valores de programación dinámica (DP) de la forma [matemática] dp [i] [j] = \ min \ limits_ {k <j} (dp [i – 1] [k] + C [ k + 1] [j]) [/ math] para alguna función de costo arbitraria [math] C [i] [j] [/ math] de modo que se pueda probar la siguiente propiedad sobre esta programación dinámica con esta función de costo. Denotemos por [matemática] A [i] [j] [/ matemática] la [matemática] k [/ matemática] óptima para la cual [matemática] dp [i] [j] = dp [i – 1] [k] + C [k] [j] [/ matemáticas]. La propiedad es que para cualquier [matemática] i [/ matemática] y [matemática] j [/ matemática], [matemática] A [i] [j] \ leq A [i] [j + 1] [/ matemática], es decir, la [matemática] k [/ matemática] óptima es monótona en [matemática] j [/ matemática] para [matemática] i [/ matemática] fija.
Un ejemplo de este DP es el siguiente problema: dados los objetos [matemáticos] n [/ matemáticos] con pesos [matemáticos] w_1, w_2, \ puntos, w_n [/ matemáticos], se dividen en grupos [matemáticos] m [/ matemáticos] de objetos consecutivos , de modo que la suma de cuadrados de los pesos totales de los grupos es mínima (el peso total del grupo es la suma de los pesos de los objetos en el grupo). Se puede demostrar que la [matemática] k [/ matemática] óptima en este problema es monótona en [matemática] j [/ matemática]. Lo mismo puede probarse si tomamos la función de costo [matemática] W \ log W [/ matemática] para el peso total [matemática] W [/ matemática] del grupo dado que todos los pesos son positivos (minimice la suma de [matemática] ] W \ log W [/ math] entre todas las distribuciones de objetos [math] n [/ math] en grupos [math] m [/ math]) o cualquier otra función convexa del peso total del grupo. En estos casos, [matemática] C [i] [j] [/ matemática] en la formulación DP sería la función de costo para un grupo con objetos desde [matemática] i [/ matemática] a [matemática] j [/ matemática] inclusivo.
La solución directa de este DP es [matemática] O (mn ^ 2) [/ matemática], porque necesitamos un ciclo sobre [matemática] i [/ matemática] ([matemática] m [/ matemática] iteraciones), un ciclo sobre [matemática] j [/ matemática] ([matemática] n [/ matemática] iteraciones) y un bucle sobre [matemática] k [/ matemática] para cada [matemática] j [/ matemática] ([matemática] n / 2 [/ matemáticas] en promedio). Sin embargo, dada la condición de monotonicidad [matemática] A [i] [j] \ leq A [i] [j + 1] [/ matemática], este DP puede resolverse en [matemática] O (mn \ log n) [/ mates]. Más específicamente, para cada [matemática] i [/ matemática] fija, resolveremos la iteración en [matemática] O (n \ log n) [/ matemática] en lugar de [matemática] O (n ^ 2) [/ matemática].
- ¿Por qué es mejor usar los elementos del marco de la colección que usar una matriz de objetos?
- ¿Cómo va a hacer que me gusten y me interesen los algoritmos (programación)?
- Si f (n) es O (g (n)) yf (n) es O (h (n)), entonces cuál de las siguientes afirmaciones debe ser verdadera: f (n) + g (n) es O (h (n)), g (n) + h (n) es O (f (n)), f (n) es O (g (n) + h (n)), o ninguno de los anteriores?
- ¿Qué algoritmos de visión por computadora se utilizan en Protracer para el vuelo de una pelota de golf?
- ¿Cómo funciona el algoritmo DeepMind?
Esto puede hacerse mediante el siguiente pseudocódigo que para [matemática] i [/ matemática] aplica divide y vencerás en [matemática] j [/ matemática] y mantiene el rango ([matemática] jleft, jright [/ matemática]) de valores de [matemática] j [/ matemática] para la cual estamos buscando la respuesta y el rango correspondiente ([matemática] kleft, kright [/ matemática]) de los valores posibles para una óptima [matemática] k [/ matemática] cuando [matemática] j [/ math] está en el rango ([math] jleft, jright [/ math]):
def ComputeDP (i, jleft, jright, kleft, kright):
# Seleccione el punto medio
jmid = (jleft + jright) / 2
# Calcular el valor de dp [i] [jmid] por definición de DP
dp [i] [jmid] = + INFINITO
bestk = -1
para k en rango (kleft, jmid):
si dp [i – 1] [k] + C [k + 1] [jmid] <mejor:
dp [i] [jmid] = dp [i – 1] [k] + C [k + 1] [jmid]
bestk = k
# Divide y conquistaras
si jleft <jmid – 1:
ComputeDP (i, jleft, jmid – 1, kleft, bestk)
si jleft + 1 <jright:
ComputeDP (i, jmid + 1, jright, bestk, kright)
def ComputeFullDP:
Inicialice dp para i = 0 de alguna manera
para i en rango (1, m):
ComputeDP (i, 0, n, 0, n)
Resulta que ComputeDP funciona para [math] O (n \ log n) [/ math] para cualquier [math] i [/ math] fijo. En realidad, una ComputeDP(i, jleft, jright, kleft, kright) funciona a tiempo [math] O (q \ log p) [/ math] donde [math] p = jright – jleft [/ math] es la longitud de el rango para [math] j [/ math] y [math] q = kright – kleft [/ math] es la longitud del rango para [math] k [/ math]. La relación de recurrencia aquí es [matemáticas] T (p, q) = O (q) + T (\ frac {p} {2}, a) + T (\ frac {p} {2}, q – a) < Bq + T (\ frac {p} {2}, a) + T (\ frac {p} {2}, q – a) [/ math] para alguna constante [math] B [/ math]. Al calcularlo aún más, vemos [matemáticas] T (p, q) <Bq + Ba + B (q – a) + T (\ frac {p} {4}, a ') + T (\ frac {p} {4}, a – a ') + T (\ frac {p} {4}, q') + T (\ frac {p} {4}, q – a – q ') = [/ matemáticas] [matemáticas ] = 2Bq + T (\ frac {p} {4}, a ') + T (\ frac {p} {4}, a – a') + T (\ frac {p} {4}, q ') + T (\ frac {p} {4}, q – a – q ') <[/ matemática] [matemática] \ ldots <[/ matemática] [matemática] <\ log_2 (p) Bq = O (q \ log p) [/ matemáticas].
