Programación Dinámica: Maximum Subarray Problem, Mínimos Cuadrados Segmentados, Problema del Viajante de Comercio

Question 1

Maximum Subarray Problem: Explicar el problema.

Answer 1

Dado un arreglo con elementos enteros, buscamos el subvector de suma máxima.

Question 2

Maximum Subarray Problem: explique la solución por fuerza bruta y su complejidad

Answer 2

Por fuerza bruta, se calculan todas las posibles sumas de cada subvector posible.
La complejidad es O(n^3)

Question 3

Maximum Subarray Problem: Explique para el algoritmo Kadane con qué se relaciona el máximo subvector.

Answer 3

El máximo subvector que termina en el elemento i está relacionado con el máximo subvector que termina en el elemento i-1.

Question 4

Kadane: Explique la relaciónde recurrencia

Answer 4

MAX(1) = v(1)

MAX(i) = max { MAX(i-1), 0 } + v[i]

Question 5

Kadane: Explique el pseudocódigo del algoritmo iterativo. ¿Qué complejidad tiene? ¿Cómo se puede obtener cuáles elementos son parte del subarray?

Answer 5

maximoGlobal  = v[1]
maximoLocal = v[1]
indexFinMax = 1

Con i desde 2 a n:
         maximoLocal = max(maximoLocal, 0) + v[i]

         Si maximoLocal > maximoGlobal:
                  maximoGlobal = maximoLocal
                  indexFinMax = i

Retornar maximoGlobal

1. Inicialmente, tanto el máximo global como el local son el primer elemento.
2. Recorro i desde 2 al n:

a. El máximo local es el máximo entre el local y 0, sumado al valor de v[i]
b. Si el local es mayor al global, actualizo el global y sumo i al índice de “fin max”.

3. Devuelvo el máximo global

=> La complejidad temporal es O(n) y la espacial es O(1), porque estamos usando únicamente 3 variables.

=> Sabiendo el índice final y la suma máxima, podemos posicionarnos en el índice final y recorrer de forma inversa restando los elementos a la suma máxima, hasta que llegue a cero. De esta forma sabremos qué elementos forman parte del subarray.

Question 6

Resolver: encontrar el subarray de suma máxima

S = [-2, -5, 6, -2, -3, 1, 5, 6]

Answer 6

=> max_total = 13 con la suma de los números [6, -2, -3, 1, 5, 6]

Question 7

Mínimos Cuadrados Segmentados: Explique el problema: ¿Qué se quiere lograr?

Answer 7

Sea un set de n puntos en el plano, ordenados tal que para cada punto, su coordenada en x es mayor que la del anterior.

Queremos aproximar mediante segmentos los puntos de P, minimizando el error cometido con la menor cantidad posible de segmentos.

La idea es que podemos generar más de un sólo segmento.

Question 8

Mínimos Cuadrados Segmentados: ¿Qué es el error cometido?

Answer 8

El error cometido va a ser la diferencia para cada punto entre su coordenada y y la posición y en la recta.

El error cometido es la suma de los errores de aproximación del segmento para los puntos que contiene ese segmento.

Siendo L la recta de aproximación L = ax + b:

E(L,P) = sumatoria desde i hasta n { ( yi - axi - b)^2}

Question 9

Mínimos Cuadrados Segmentados: explique el concepto de penalidad

Answer 9

Queremos lograr soluciones con la menor cantidad de segmentos, pero minimizando el error de aproximación. Para eso, proponemos una penalidad C > 0 por cada segmento añadido. A mayor valor de C, menos segmentos tendremos. A menor, más segmentos.

Question 10

Mínimos Cuadrados Segmentados: Explique la solución por fuerza bruta con sus complejidades.

Answer 10

Cada punto puede ser el final o no de un segmento. Se puede representar esto con un vector de tamaño n, donde en cada posición se tiene un 1 si el punto es final de un segmento, o 0 en otro caso.

Se tendrían que analizar posibles combinaciones. Para cada una, el cálculo de los segmentos es O(n) y el cálculo del error cometido es O(n).
Como existen 2 ^n combinaciones, la complejidad total es O((2^n) * n).

Question 11

Mínimos Cuadrados Segmentados: Explique parala solución iterativa la relación de recurrencia

Answer 11

El punto pn pertenece al último segmento. Este segmento inicia en un px anterior.

Si en la solución óptima conocemos el último segmento, conocemos el error entre x-n que se está cometiendo para ese segmento.

Podemos ver que:

• El óptimo para el último punto n es el error cometido en el segmento (penalidad) + el costo del segmento + el optimo de los puntos x-1:

OPT(n) = e(x,n) + C + OPT(x-1)

Queremos elegir como último segmento a aquel que minimice el error general

OPT(N) = min { e(x,n) + C + OPT(x-1) } ; con 1 <= x <= n

Podemos generalizar el problema como:

OPT(i) = min { e(x,n) + C + OPT(x-1) } ; con 1 <= x <= i
OPT(0) = 0

Question 12

Mínimos Cuadrados Segmentados: Explique el pseudocódigo. ¿Qué complejidad tiene?

Answer 12

OPT[0] = 0

Para todo posible segmento [i,j] con i <=j:
      calcular e_i,j

Con j desde 1 hasta n:

      OPT[j] = +inf

      Con i desde 1 hasta n:
            segmento = e[i][j] + C + OPT[i-1]

            si OPT[j] > segmento:
                  OPT[j] = segmento

Retornar OPT[n]

1. El óptimo de 0 es 0.
2. Para todos los posibles segments, calculamos el error.
3. Con j desde 1 a n:

a. Inicializamos los optimos de j en +inf
b. Con i de 1 a n:
- calculo el segmento como la suma del error para los dos puntos, la penalidad y el óptimo del punto anterior sobre el eje x
- Si el óptimo de j > segmento: actualizo el valor de óptimo de j con el segmento.

4. Retorno OPT[n]

=> Complejidad temporal: el cálculo de cada óptimo es O(n) y se calculan n óptimos: O(n^2). Además para todos los pares posibles, se calcula el error en O(n).

Complejidad temporal final: O(n^3), lo cual sigue siendo mejor que O(2^n * n).
Complejidad espacial: O(n^2).

Question 13

Problema del Viajante de Comercio: Explicarlo.

Answer 13

Sean:
- Un conjunto de n ciudades C
- Un conjunto de rutas con costo de tránsito
- Existe una ruta para cada par de ciudades
- El costo de cada ruta puede o no ser simétrico (mismo valor de ida y de vuelta).

Queremos obtener el circuito de menor costo que inicie y finalice en una ciudad inicial y pase por el resto de las ciudades una y sólo una vez.

Question 14

Problema del Viajante de Comercio: explique la solución por fuerza bruta e indique su complejidad.

Answer 14

• La solución por fuerza bruta requiere de calcular todos los ciclos posibles.
• Existen (n-1)! ciclos de longitud (n-1).
• Para cada uno, calculamos su costo O(n).

=> La complejidad entonces es de O( n * (n-1) ! ) => O(n!)

Question 15

Problema del Viajante de Comercio: Explique la descomposición del algoritmo de Bellman-Held-Karp en un árbol y la relación de recurrencia

Answer 15

Se descompone el problema en forma de árbol, con (n-1)! hojas.

Luego, vemos que podemos usar memorización porque hay ramas repetidas.

El óptimo del problema va a ser el mínimo entre los subproblemas menores.

OPT (i, S ) = min { w(i, j) + OPT ( j, S− j ) }  con j en S
OPT (i,∅) = w (i ,start); siendo start: ciudad inicial

Question 16

Bellman-Held-Karp: explique la solución iterativa, junto con su complejidad.

Answer 16

Siendo i las ciudades
C al conjunto de todas las ciudades
1 a la ciudad inicial

// Para todas las ciudades, calculo el camino de vuelta a 1
Con i de 2 a n:
         OPT[i][∅] = W[i][1]

Con k de 1 a n-2:
         Para todo subset S de C-{1} que tenga tamaño k:

                  Para cada elemento i de S:
        									// La distancia de i a cualquier elemento del conjunto S-{i}
                           OPT[i][S-{i}] = +inf

                           Por cada elemento j de S-{i}:
                           // Calculo la distancia de i al conjunto S-{i,j}, conectando a i con los distintos j
                                    r = OPT[j][ S-{i,j} ]+ w[j][i]

                                    Si r < OPT[i, S-{i}] :
                                             OPT[i][S-{i}] = r

caminoMinimo = +inf

Con i de 2 a n:
         ciclo = OPT[i, S-{1,i}] + w[1][i]

         Si caminoMinimo > ciclo:
                  caminoMinimo = ciclo

Retornar caminoMinimo

La complejidad temporal es O(n^2 * 2^n). No es polinomial pero es mejor que factorial si los n son muy grandes.
Hasta 5 ciudades conviene hacerlo con fuerza bruta. Sino, de forma iterativa.