Post on 19-Oct-2015
Programacion dinamica
Problemas, algoritmos y programacion
31 de Agosto 2011
Problemas, algoritmos y programacion Programacion dinamica
Problema: diff
El comando diff
diff es un comando de Linux que muestra las diferencias en elcontenido de dos textos (equivalente a fc.exe de Windows/DOS)
Cuando se usa?
Se usa, entre otras cosas, para comparar ediciones (versiones) deun mismo archivo
Como compara?
El criterio por defecto es buscar lneas comunes a ambos archivos.
Problemas, algoritmos y programacion Programacion dinamica
Problema: diff - Ejemplo
Nueva version/**
* main class of diff program */
*/
class Diff {
/* calculate common lines */
int commonLines(File a, File b) {
String contentA = read(a); //fixed
String contentB = read(b);
ParsedText pA = parse(contentA);
ParsedText pB = parse(contentB);
int result = LCS.calculate(pA, pB);
return result;
}
}
Version originalclass Diff {
int commonLines(File a, File b) {
String contentA = read(b);
String contentB = read(b);
String[] pA = split(contentA);
String[] pB = split(contentB);
int result = LCS.calculate(pA, pB);
return result;
}
}
Referencia de colores
lneas sin cambios lneas nuevas lneas eliminadas
Problemas, algoritmos y programacion Programacion dinamica
Problema: diff
Operaciones de moficiacion
Sin operacion : las lneas comunes
Insercion : las lneas no comunes del nuevo
Borrado : las lneas no comunes del original
Cual es el problema?
Para hacer una buena comparacion de archivos, hay que tener unalgoritmo que encuentre la mayor cantidad de lneas comunes entreambos. Ademas, las lneas comunes tienen que aparecer con elmsmo orden en ambos archivos.
Problemas, algoritmos y programacion Programacion dinamica
Problema: diff
Generalizacion
A este problema se lo conoce como encontrar la sub-secuenciacomun de mayor longitud (o Longest Common Subsequence)
Longest Common Subsequence
Entrada: dos sequencias (vectores, arreglos) A y B
Salida: la longitud de la sub-secuencia comun a A y a B maslarga posible
LCS : (T [],T []) int
Ejemplos
LCS([X AABBDZ ], [AX ACBDY ]) = 4
LCS([], [XXYY ]) = 0
LCS([123456], [123456]) = 6
LCS([], []) = 3Problemas, algoritmos y programacion Programacion dinamica
Problema: diff - Como se puede resolver?
Mas problemas
Se calculan las LCS de todos los prefijos de A contra todos losprefijos de B
Entre estos resultados esta la LCS de A y B
Si n y m son el tamano de A y B, la cantidad de LCS que sevan a calcular son (n + 1)(m + 1)
Cada prefijo de A se puede identificar con su longitud, que esun numero del 0 al n. De la misma forma, cada prefijo de Bse identifica con los numeros del 0 al m.
LCS2 : (int, int,T [],T []) int
Problemas, algoritmos y programacion Programacion dinamica
Problema: diff - Como se puede resolver?
Ejemplo con los archivos
Prefijo 8/**
* main class of diff program */
*/
class Diff {
/* calculate common lines */
int commonLines(File a, File b) {
String contentA = read(a); //fixed
String contentB = read(b);
Prefijo 5class Diff {
int commonLines(File a, File b) {
String contentA = read(b);
String contentB = read(b);
String[] pA = split(contentA);
Algunos valores de LCS2
LCS2(8, 5, nuevo, original) = 3
LCS2(4, 1, nuevo, original) = 1
LCS2(5, 0, nuevo, original) = 0
LCS2(5, 1, nuevo, original) = 1
LCS2(6, 2, nuevo, original) = 2
Problemas, algoritmos y programacion Programacion dinamica
Problema: diff - Como se puede resolver?
Caso 1/3 - Base
Alguno de los dos prefijos tiene longitud 0, entonces la LCS es 0LCS2(0, , , ) = 0LCS2( , 0, , ) = 0
Problemas, algoritmos y programacion Programacion dinamica
Problema: diff - Como se puede resolver?
Caso 2/3 - Terminan igual
Los dos prefijos terminan con el mismo elemento, entonces hay unaLCS para estos prefijos que termina en este elemento comun.
Ejemplo con los archivos
Prefijo 6/**
* main class of diff program */
*/
class Diff {
/* calculate common lines */
int commonLines(File a, File b) {
Prefijo 2class Diff {
int commonLines(File a, File b) {
Cuanto vale LCS2?
A[i 1] = B[j 1] LCS2(i , j ,A,B) =1 + LCS2(i 1, j 1,A,B)
Problemas, algoritmos y programacion Programacion dinamica
Problema: diff - Como se puede resolver?
Caso 3/3 - Terminan distinto
Los dos prefijos terminan con distintos elementos, entonces hayuna LCS para estos prefijos que no usa, al menos, una terminacion.
Ejemplo con los archivos
Prefijo 6/**
* main class of diff program */
*/
class Diff {
/* calculate common lines */
int commonLines(File a, File b) {
Prefijo 3class Diff {
int commonLines(File a, File b) {
String contentA = read(b);
Cuanto vale LCS2?
A[i 1] 6= B[j 1] LCS2(i , j ,A,B) =max
{LCS2(i , j 1,A,B)LCS2(i 1, j ,A,B)
Problemas, algoritmos y programacion Programacion dinamica
Problema: diff - Como se puede resolver?
Definicion partida de LCS2
LCS2(i , j ,A,B) =
0 i = 0 j = 0
1 + LCS2(i 1, j 1,A,B) A[i 1] = B[j 1]
max
{LCS2(i , j 1,A,B)LCS2(i 1, j ,A,B) A[i 1] 6= B[j 1]
LCS en base a LCS2
LCS(A,B) = LCS2( largo(A), largo(B),A,B )
Problemas, algoritmos y programacion Programacion dinamica
Problema: diff - Como se puede programar?
Primeras consideraciones
Si se dispone de la funcion LCS2, la funcion LCS se programamuy simplemente
La funcion LCS2 se puede programar recursivamente
Los argumentos A y B de LCS2 son siempre los mismos
Entonces LCS2 se puede programar como una funcionrecursiva de dos variables (los prefijos i y j). Los arreglos A yB se pueden considerar como variables globales
El caso base de la recursion es cuando i = 0 o j = 0
Problemas, algoritmos y programacion Programacion dinamica
Problema: diff - Como se puede programar?
Una cosa mas: el arbol de llamadas
Para calcular LCS2(i , j) senecesita el valor de LCS2(i1, j), LCS2(i , j1) y LCS2(i1, j1).
i , j
i , j 1
i 1, j
i , j 2
i 1, j 1
i 2, j
i , j 3
i 1, j 2
i 2, j 1
i 3, j
Hay multiples llamadas iguales!La funcion LCS2 recorre todas las sub-sequencias comunes. No hacer la misma llamada dos veces es fundamentalpara resolver el problema con una complejidad temporal optima
Problemas, algoritmos y programacion Programacion dinamica
Problema: diff - Como se puede programar?
Primer programa: recursion memorizada (memoization)T[] A, B;
int mem[][];
int lcs(T[] a, T[] b) {
A = a; B = b;
int n = length(A), m = length(B);
init(mem, n+1, m+1, -1);
return lcs2(n, m);
}
int lcs2(int i, int j) {
if( mem[i][j] == -1 ) {
if( i == 0 || j == 0 ) {
mem[i][j] = 0;
} else if( A[i-1] == B[j-1] ) {
mem[i][j] = 1 + lcs2(i - 1, j - 1);
} else {
mem[i][j] = max(lcs2(i - 1, j), lcs2(i, j - 1));
}
}
return mem[i][j];
}
Observacion
Este programa calcula todos los valores de la funcion LCS2 en lamatriz mem
Problemas, algoritmos y programacion Programacion dinamica
Problema: diff - Como se puede programar?
Recursion vs. Calculo de valores de la matriz mem
0, 0 0, 1 0, 2 0, 3 0, 4 0, 5 0, 6 0,m
1, 0 1, 1 1, 2 1, 3 1, 4 1, 5 1, 6 1,m
2, 0 2, 1 2, 2 2, 3 2, 4 2, 5 2, 6 2,m
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.. . .
.
.
.
n, 0 n, 1 n, 2 n, 3 n, 4 n, 5 n, 6 n,m
Recursion (dependencia)
i , j 1
i 1, j 1
i , j
i 1, jCalculo de mem
n, 0
0, 0
n,m
0,m
Problemas, algoritmos y programacion Programacion dinamica
Problema: diff - Como se puede programar?
Observacion
Se puede eliminar la recursion calculando los valores de memdirectamente. El orden en que se vayan calculando los valores debesatisfacer todas las dependencias.
Segundo programa: sin recursionint mem[][];
int lcs(T[] A, T[] B) {
int n = length(A), m = length(B);
init(mem, n+1, m+1, -1);
for(i : 0 ... n) {
for(j : 0 ... m) {
if( i == 0 || j == 0 ) {
mem[i][j] = 0;
} else if( A[i-1] == B[j-1] ) {
mem[i][j] = 1 + mem[i - 1][j - 1];
} else {
mem[i][j] = max(mem[i - 1, j], mem[i, j - 1]);
}
}
}
return mem[n][m];
}
Problemas, algoritmos y programacion Programacion dinamica
Problema: diff - Como se puede programar?
Segundo programa: sin recursion
La complejidad temporal es O(n.m)
La complejidad espacial es O(n.m). Se puede hacer mejor?
Se puede hacer en complejidad espacial O(n + m) (optimo).
Observacion: La comparacion de elementos
La complejidad temporal O(n.m) asume que la comparacionde elementos es O(1) (constante)
Si son elementos complejos se puede hacer un hashing inicialde los mismos para facilitar la comparacion
Observacion: Obtener la sub-sequencia
El algoritmo presentado calcula solo la longitud, pero siguiendo latabla de atras hacia adelante se puede obtener una sub-sequenciacomun de mayor longitud
Problemas, algoritmos y programacion Programacion dinamica
Programacion dinamica
Introduccion
Programacion Dinamica es una tecnica para resolver cierto tipode problemas (como LCS)
Problemas, algoritmos y programacion Programacion dinamica
Programacion dinamica: Definiciones
Problema
Un problema define un valor buscado (resultado) sobre ciertosparametros genericos (entrada)
Ejemplo: LCS
Entrada: Dos arreglos
Resultado: La longitud de la sub-secuencia comun mas larga
Ejemplo: Ordenamiento
Entrada: Un arreglo
Resultado: Un arreglo con los elementos ordenados
Ejemplo: SAT
Entrada: Un sistema de ecuaciones booleanas
Resultado: La satisfacibilidad del sistema
Problemas, algoritmos y programacion Programacion dinamica
Programacion dinamica: Definiciones
Instancia de un problema
Es un problema con parametros de entrada concretos (nogenericos). Toda instancia tiene un resultado definido.
Ejemplo: LCS
LCS de XAABBDZ y AXACBDY 4LCS de 123456 y 123456 6
Ejemplo: Ordenamiento
Ordernar: [perro,casa,gato] [casa,gato,perro]Ordernar: [0, 3, 0, 3, 4, 5, 6] [0, 0, 3, 3, 4, 5, 6]
Ejemplo: SAT
El sistema
{a bb (a b) es satisfacible? S
Problemas, algoritmos y programacion Programacion dinamica
Programacion dinamica: Definiciones
Problema recursivo
En un problema recurisvo el resultado de una instancia se puedeobtener en base a otros resultados de instancias mas chicas delmismo problema (sub-problemas / sub-instancias)
Ejemplo: LCS
El resultado se puede obtener combinando resultados de losprefijos.
Ejemplo: Ordenamiento
El resultado se puede obtener encontrando el menor,intercambiarlo con el primero y ordenando el resto (Selectionsort)
El resultado se puede obtener ordenando dos mitades delarreglo y combinando ambos resultados (Merge sort)
Problemas, algoritmos y programacion Programacion dinamica
Programacion dinamica: Aplicaciones
Sub-problemas
La programacion dinamica es util si la cantidad desub-problemas es abaracable computacionalmente
Ejemplos: LCS y Ordenamiento
Mal ejemplo: SAT (por algo es NP completo)
Sub-problemas superpuestos
La programacion dinamica es util si distintos sub-problemas sepueden resolver en base a sub-sub-problemas comunes
Ejemplo: LCS (as se ve en el arbol de llamadas)
Mal ejemplo: Merge sort
Principio de optimalidad
La solucion de un problema esta formada por soluciones desub-problemas (sub-soluciones)
Problemas, algoritmos y programacion Programacion dinamica
Programacion dinamica: Aplicaciones
Principio de optimalidad - Ejemplos
Camino mnimo: Si el camino mas corto de A a B pasa por C,ese camino esta formado por un camino mnimo de A a C yotro de C a B
LCS: La solucion contiene pedazos que son LCS de sus prefijos
Principio de optimalidad y recursion
Un problema que cumpla con el principio de optimalidad se puedeabaracar como problema recursivo
sub-problemas sub-soluciones
Problemas, algoritmos y programacion Programacion dinamica
Programacion dinamica: Resumen
Problemas
Con sub-problemas
Que cumplan el principio de optimalidad
Superpuestos
Algoritmos
Enfoque recursivo
Induccion / Induccion estructural
Divide & Conquer
Programacion
Memoization (funcion recursiva memorizada)
Llenado de tabla
Problemas, algoritmos y programacion Programacion dinamica
Problema: Distancia de edicon (Edit Distance)
Problema
Encontrar la menor cantidad de ediciones para llegar de unapalabra a otra.
Operaciones de edicion
Eliminacion de una letra
Insercion de una letra
Substitucion de una letra
Ejemplo: gato blancogato (g b) bato (+ n) banto (+ l) blanto (t c) blancoLa distancia de edicion es 4
Problemas, algoritmos y programacion Programacion dinamica
Problema: Distancia de edicon (Edit Distance)
Variantes del problema
Las variantes del problema se dan al cambiar las operacionesposibles
Solo con eliminacion e insercion se reduce a LCS
Eliminacion, insercion y substitucion: distancia de Levenshtein
Agregando transposicion de letras: distancia deLevenshtein-Damerau
Todas esta variantes se pueden resolver usando programaciondinamica
Usos comunes
Corregir errores de tipeo
Deteccion de fraude
Encontrar variaciones en ADN
Problemas, algoritmos y programacion Programacion dinamica
Problema: Distancia de edicon (Edit Distance)
Edit distance
Entrada: dos cadenas A y B
Salida: la distancia de Levenshtein entre A y a B
LEV : (String ,String) int
Una solucion con programacion dinamica
Enfoque similar al usado en LCS
Se calculan las distancias de todos los prefijos de A a todoslos prefijos de B
LEV2 : (int, int,String , String) int
Problemas, algoritmos y programacion Programacion dinamica
Problema: Distancia de edicon (Edit Distance)
Determinar LEV2 (similar a LCS2)
Caso base: alguno de los prefijos tiene longitud 0, la distanciaes la longitud del otro
Terminan igual: lo optimo es que esas letras secorrespondan y no se haga ninguna operacion al final de ALEV ( gato, blanco ) = LEV ( gat, blanc )
Terminan distinto: se tiene que aplicar alguna operacion alfinal de ALEV ( gat, blanc ) es el mnimo de:(insertar c) 1 + LEV ( gatc, blanc )(insertar c) 1 + LEV ( gat, blan )(borrar t) 1 + LEV ( ga, blanc )(t c) 1 + LEV ( gac, blanc )(t c) 1 + LEV ( ga, blan )
Problemas, algoritmos y programacion Programacion dinamica
Problema: Distancia de edicon (Edit Distance)
Definicion partida de LEV2
LEV2(i , j ,A,B) =
i + j i = 0 j = 0
LEV2(i 1, j 1,A,B) A[i 1] = B[j 1]
1 + min
LEV2(i , j 1,A,B)LEV2(i 1, j ,A,B)LEV2(i 1, j 1,A,B)
A[i 1] 6= B[j 1]
Problemas, algoritmos y programacion Programacion dinamica
Problema: Distancia de edicon (Edit Distance)
Posible implementacion (sin recursion)int mem[][];
int lev(T[] A, T[] B) {
int n = length(A), m = length(B);
init(mem, n+1, m+1, -1);
for(i : 0 ... n) {
for(j : 0 ... m) {
if( i == 0 || j == 0 ) {
mem[i][j] = i + j;
} else if( A[i-1] == B[j-1] ) {
mem[i][j] = mem[i - 1][j - 1];
} else {
mem[i][j] = 1 + min(mem[i - 1, j], mem[i, j - 1], mem[i - 1, j - 1]);
}
}
}
return mem[n][m];
}
Observaciones
El orden de llenado satisface las dependencias
Complejidad temporal: O(n.m), espacial: O(n.m)
Se puede lograr complejidad espacial O(n + m)
Problemas, algoritmos y programacion Programacion dinamica
Otros problemas de cadenas
Transformar en palndromo
Problema: Dada una cadena, encontrar la mnima cantidad deediciones para transformarla en palndromo (capicua)
Sub-problemas a considerar: todas las sub-cadenas (recortes)de la original. Complejidad temporal: O(n2)
Compresion RLE (run-length encoding)
Problema: Dada una cadena, encontrar una compresion RLEde tamano mnimo. Un ejemplo de compresion RLE de lacadena XAABCBCBCAABCBCBCX es X2(2A3(BC))X.
Sub-problemas a considerar: todas las sub-cadenas (recortes)de la original.
Tambien hay que detectar cuales sub-cadenas sonrepeticiones. AABCBCBCAABCBCBC 2(AABCBCBC)Complejidad temporal: O(n3)
Problemas, algoritmos y programacion Programacion dinamica
Problema: Mayor sub-sequencia creciente
Descripcion
Dada una sequencia de numeros, encontrar el maximo largode una sub-sequencia con sus elementos en ordenestrictamente creciente
LIS : (int[]) int
Ejemplos
LIS([0, 8, 4, 12, 2, 10, 6, 14, 6, 9, 5]) 4LIS([2, 3, 7, 10, 15]) 5LIS([]) 0LIS([15, 10, 7, 3, 2]) 1
Solucion O(n2) usando LCS
Una sub-sequencia creciente de A es una sub-sequencia
comun entre A y A ordenada (~~A). LIS(A) = LCS(A,
~~A)
Problemas, algoritmos y programacion Programacion dinamica
Problema: Mayor sub-sequencia creciente
Considerando otros sub-problemas y sub-soluciones
De todas las sub-secuencias de un mismo tamano siempre esmas util la que termina en lo menor posible
Para cada prefijo Ai y cada tamano j , se busca la terminacionoptima de una sub-sequencia creciente. j [1, LIS(Ai )]Si Ti [j ] son estos valores, entonces Ti es creciente y sutamano es LIS(Ai )
Definicion recursiva de T [i ]
T1[1] = A[0] (caso base)
Todos los valores de Ti+1 son iguales a los de Ti excepto:
Si A[i ] Ti [1] Ti+1[1] = A[i ]Si A[i ] > Ti [LIS(Ai )] Ti+1[LIS(Ai ) + 1] = A[i ]Si Ti [j ] < A[i ] Ti [j + 1]] Ti+1[j + 1] = A[i ]El valor que cambia se puede encontrar con busqueda binaria
Problemas, algoritmos y programacion Programacion dinamica
Problema: Mayor sub-sequencia creciente
Posible implementacionint lis(int[] A) {
if( length(A) == 0 ) return 0;
int[] T = [ A[0] ];
for(i : 1 ... length(A)) {
if ( A[i]
Problema: Calculo de probabilidades
Calcular la problabilidad de:
tirar un dado 6 veces y sumar 20
tirar una moneda 20 veces y sacar 11 caras
Algunos calculos de probabilidad se pueden plantear recursivamente
Ejemplo
La probabiliad de tirar un dado 6 veces y sumar 20 es la suma de
+ 1/6 la probabilidad de tirar un dado 5 veces y sumar 19+ 1/6 la probabilidad de tirar un dado 5 veces y sumar 18+ 1/6 la probabilidad de tirar un dado 5 veces y sumar 17+ 1/6 la probabilidad de tirar un dado 5 veces y sumar 16+ 1/6 la probabilidad de tirar un dado 5 veces y sumar 15+ 1/6 la probabilidad de tirar un dado 5 veces y sumar 14
Problemas, algoritmos y programacion Programacion dinamica
Problema: Calculo de probabilidades
Generalizacion
Los problemas:
tirar un dado 6 veces y sumar 20
tirar una moneda 20 veces y sacar 11 caras
se pueden generalizar a calcular la probabilidad de sumar s tirandon veces un dado de d caras. P(s, n, d) [0, 1]
Definicion recursiva
P(0, 0, ) = 1 y P( , 0, ) = 0
P(s, n, d) =d
i=11d P(s i , n 1, d)
Observaciones
Hay sub-problemas superpuestos
d es siempre el mismo
Complejidad temporal: O(s.n.d) y espacial: O(s.n)
Problemas, algoritmos y programacion Programacion dinamica
Programacion dinamica y juegos
Juegos
Algunos juegos pueden ser analizados con programacion dinamica.En especial aquellos que sean:
por turnos
finitos y sin empate
Que se puede analizar?
Si un estado del juego es ganador o perdedor
Si existe alguna estrategia ganadora
En cuantas jugadas termina
Como se pueden analizar estos juegos recursivamente?
Los estados terminales del juego son los casos bases
Un estado no terminal es ganador si existe una jugada quelleva a un estado perdedor (no ganador)
Problemas, algoritmos y programacion Programacion dinamica
Programacion dinamica sobre subconjuntos
Problema: el viajante de comercio
Entrada: un conjunto de n ciudades y los costos cij de viajarde la ciudad i a la j . 0 i , j < nSalida: el costo del itinerario mas barato que visita todas lasciudades una sola vez
C (int, int[][]) int
Sub-problemas
El itinerario mas barato para todos los sub-conjuntos de ciudades(sub-grafo inducido) y todas sus terminaciones.
La cantidad de sub-grafos es 2n
La cantidad de sub-problemas es O(2n.n)
C2(int, int[][], SubConjunto, int) intC (n, c) = min0i
Programacion dinamica sobre subconjuntos
Definicion recursiva de C2
C2( , , {t}, t) = 0C2(n, c ,S , t) = miniS{t}{c[i ][t] + C2(n, c ,S {t}, i)}
Manipulacion de sub-conjuntos (mascara de bits)
Los sub-conjuntos de un conjunto de n elementos se puedenasociar, uno a uno, con los numeros del 0 al 2n
El sub-conjunto S se representa con el numerom(S) =
iS 2
i
El numero s representa al sub-conjuntoS = {i [0, n 1]/biti (s) = 1}Si T S m(T ) < m(S)Si t S (m(S)&2t) = 2t (& es el and de bits)Si t S m(S {t}) = m(S) 2t
Problemas, algoritmos y programacion Programacion dinamica
Programacion dinamica sobre subconjuntos
Nueva definicion recursiva de C2
C2(int, int[][], int, int) intC2( , , 2
t , t) = 0
C2(n, c ,m, t) = minm&2i=2ii 6=t{c[i ][t] + C2(n, c,m 2t , i)}
Dependencias de C2
El valor de C2(n, c ,m(S), t) depende de los valores de C2 paratodos los sub-conjuntos de S
Los sub-conjuntos de S se representan con un numero menora m(S)
C2 se puede calcular en orden creciente de m(S)
Problemas, algoritmos y programacion Programacion dinamica
Programacion dinamica sobre subconjuntos
Posible implementacionint C(int n, int[][] c) {
int mem[1