• Author / Uploaded
• 123uni

Citation preview

Programaci´on Din´amica

V´ıctor Racs´o Galv´an Oyola

November 2016

´Indice general

1. Introducci´ on

3

1.1. ¿A qu´e nos referimos con Programaci´on Din´amica? . . . . . . . . . . . . . . . . . . .

3

1.2. Soluciones con Programaci´ on Din´amica . . . . . . . . . . . . . . . . . . . . . . . . . .

3

2. Problemas T´ıpicos de Programaci´ on Din´ amica

4

2.1. M´ axima Suma de Rango de 1 Dimensi´on (Max 1D Range Sum) . . . . . . . . . . . .

4

2.2. M´ axima Suma de Rango de 2 Dimensiones (Max 2D Range Sum) . . . . . . . . . .

5

2.3. Corte de Barra (Rod Cutting) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

2.4. Multiplicaci´ on de Cadenas de Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

2.5. Subsecuencia Com´ un M´ as Larga (Longest Common Subsequence LCS) . . . . . . .

11

2.6. Subsecuencia Creciente M´ as Larga (Longest Increasing Subsequence LIS) . . . . . .

12

2.7. Problema de la Mochila (Knapsack Problem) . . . . . . . . . . . . . . . . . . . . . . .

14

2.8. Cambio de Monedas (Versi´ on General) . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

2.9. Problema del Cartero (Travelling Salesman Problem) . . . . . . . . . . . . . . . . . .

17

2.10. Alineamiento de Cadenas (Edit Distance) . . . . . . . . . . . . . . . . . . . . . . . . .

18

3. Problemas No T´ıpicos de Programaci´ on Din´ amica

21

3.1. Subsecuencia Pal´ındroma M´ as Larga (Longest Palindromic Subsequence) . . . . . .

21

3.2. LIS con Binary Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

3.3. Subsecuencia Bit´ onica M´ as Larga (Longest Bitonic Subsequence) . . . . . . . . . . .

25

3.4. Subsecuencia Ordenada M´ as Larga (Versi´on General) . . . . . . . . . . . . . . . . . .

27

3.5. Particionamiento de Pal´ındromos (Minimum Palindrome Partitioning) . . . . . . .

28

1

´INDICE GENERAL 3.6. Encadenamiento Lineal (One-Dimensional Chaining Problem) . . . . . . . . . . . . .

4. Elementos de la Programaci´ on Din´ amica

2 31

34

´ 4.1. Subestructura Optima de la soluci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . .

34

4.1.1. Estado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

34

4.2. Sutilezas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

34

4.3. Subproblemas Sobrelapados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

34

´ 4.4. Reconstruyendo la Soluci´ on Optima . . . . . . . . . . . . . . . . . . . . . . . . . . . .

34

4.5. Almacenamiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

34

Cap´ıtulo 1

Introducci´ on 1.1.

¿A qu´ e nos referimos con Programaci´ on Din´ amica?

Ya hemos escuchado sobre los algoritmos “Dividir y Conquistar”, los cuales dividen un problema en subproblemas y los resuelven para luego obtener la respuesta total combinando las subrespuestas. Por su parte, la Programaci´on Din´amica o DP (Dynamic Programming) se aplica cuando los subproblemas se sobreponen, es decir, los subproblemas comparten parcialmente sus respuestas. En tal caso, los algoritmos “Dividir y Conquistar” hacen mucho m´as trabajo que el necesario, resolviendo m´ ultiples veces la misma porci´on de problema. La programaci´on din´amica resuelve cada subproblema y guarda esa respuesta, con el fin de que ahorrarnos el tener que volver a procesar el problema en ese punto y solamente se usan los datos guardados, siendo m´as eficientes de esa manera. Esto puede sonar muy confuso, pero recordemos el tema de backtracking. Por lo general, este se plantea en los problemas que tengan k opciones de acci´on en cada paso u objeto del problema, formando un ´ arbol k´ario al desarrollar todas las respuestas posibles. Considerando cada uno de los sub´ arboles de acci´ on, es muy probable que algunos se repitan: aqu´ı es donde aplicamos la programaci´ on din´ amica. Es com´ un usar DP en problemas de optimizaci´ on. Este tipo de problemas puede tener diferentes formas de obtener el valor ´ optimo (sea m´aximo o m´ınimo), por lo que el DP va a hallar una soluci´ on ´ optima no necesariamente u ´nica.

1.2.

Soluciones con Programaci´ on Din´ amica

Para resolver problemas determinados con DP, se deben seguir algunos pasos necesarios y otros complementarios al plantear el algoritmo. En principio debemos definir una estructura ´ optima para poder procesar correctamente la soluci´on. En segundo lugar, debemos hallar una recursi´ on para obtener la soluci´ on ´ optima, para luego calcularla con nuestro programa. Un paso extra usualmente solicitado en los problemas es reconstruir una posible soluci´on ´optima o hallar una que cumpla con determinadas caracter´ısticas para volverla u ´nica (puede ser orden lexicogr´ afico, la que tenga mayor cantidad de estados atravesados, etc.)

3

Cap´ıtulo 2

Problemas T´ıpicos de Programaci´ on Din´ amica 2.1.

M´ axima Suma de Rango de 1 Dimensi´ on (Max 1D Range Sum)

Una forma reducida del enunciado del problema 507 del UVa es la siguiente: Dado un arreglo A con n ď 20K “ 20. 103 elementos diferentes de 0, determinar la m´axima suma de rango de A.

Esto, en otras palabras, significa que debemos hallar el Range Sum Query(RSQ) entre dos ´ındices i y j pertenecientes al intervalo r0, n ´ 1s. Vi´endolo: # j + ÿ Respuesta “ max Ak @i, j “ 0, 1, 2, . . . , n ´ 1 k“i

Un algoritmo de B´ usqueda Completa (Complete Search) tomar´ıa Opn2 q para probar todos los pares pi, jq P r0, n ´ 1s ˆ r0, n ´ 1s Ă Z2 junto con Opnq para procesar el RSQ, con lo cual se ejecutar´ıa con un tiempo de Opn3 q. Con n ď 20K, esta soluci´on dar´ıa TLE. Una estrategia con DP ser´ıa pre-procesar el arreglo de forma que el valor de A1k sea la suma de todos los valores anteriores junto con el del mismo Ak , podemos plantear el bucle siguiente:

A[i] += A[i-1], i=1,2,3,...,n-1 Ahora podremos procesar el RSQ en Op1q:

Cuando i “ 0 RSQ(0,j) = A[j] y RSQ(i,j) = A[j]-A[i-1], @i ą 0 Con esto, el algoritmo de b´ usqueda completa procesa la respuesta en Opn2 q, sin embargo, con n ď 20K da igual TLE. A pesar de todo, esta t´ecnica suele funcionar en otros casos. Para este 4

´ DINAMICA ´ CAP´ITULO 2. PROBLEMAS T´IPICOS DE PROGRAMACION

5

problema hay incluso un algoritmo m´ as adecuado: El algoritmo de Jay Kadane para el problema del m´ aximo subarreglo. Este se ejecuta en Opnq tomando una visi´on algo greedy con el DP, es de la forma siguiente: #include