Diseño y Análisis de Algoritmos con Java Dr.Eric...

Diseño y Análisis de Algoritmos con Java Dr.Eric Jeltsch F.

____________________________________________________________________ Ingeniería en Computación, Universidad de La Serena

1

Técnicas Algorítmicas. A continuación estudiaremos algunas técnicas generales para la construcción de algoritmos. Cada una de estas técnicas tienen características especiales que las hacen apropiados para resolver ciertos tipos de problemas. Desde luego una técnica siempre podrá tener alguna ventaja o desventaja respecto de otra. Lo importante, en todo caso, es enfrentar medológicamente la construcción de algoritmos que obedecen a ciertas estrategias. Sin embargo, debo insistir en que no se deberían aplicar estas técnicas en forma indiscriminada a cualquier problema. En general, la estructura del problema determina habitualmente la posibilidad de aplicación de una técnica específica. Sin embargo, considerar que muchos problemas pueden resolverse buscando una solución fácil y directa pero, a la vez bastante ineficiente. Este método, llamado de fuerza bruta, puede ser muy directo, pero con un poco de análisis puede encontrarse algoritmos más eficientes. El esquema mas sencillo quizás sea el llamado divide y vencerás, basado en la descomposición de un problema en subproblemas. Otros esquemas requieren un análisis minucioso del problema de forma que la solución se vaya construyendo en etapas. Si puede preverse que decisión conviene en cada etapa para producir cierto tipo de mejor resultado, tenemos una solución voraz, si la decisión en una etapa, solo puede tomarse tras considerar varias soluciones de otras etapas mas simples, la solución es dinámica. Aun así, hay problemas cuya solución no puede hallarse sino mediante un proceso de búsqueda, a pesar de lo complejas que son las operaciones de búsqueda, su uso adecuado mediante el esquema de búsqueda con retroceso (o backtracking) permite ganar gran eficiencia respecto a soluciones de fuerza bruta. Por ultimo, conviene conocer otros métodos de diseño de algoritmos que también resultan de utilidad práctica. Otro no menos importante, por la diversidad de campos de aplicación es la programación dinámica, muy útil en la asignatura de Investigación de Operaciones, por ejemplo, en donde se utiliza el empleo de tablas o arreglos matriciales como estructura auxiliar para la resolución eficiente del problema. Las técnicas que se abordan son: a) Fuerza Bruta, b) Divide y Vencerás, c) Programación Dinámica y d) Algoritmos Avidos (Greedy). e) Backtracking a) Fuerza Bruta Los algoritmos de Fuerza Bruta se caracterizan por una falta de sofisticación en la solución. En general, se toma la ruta más directa, sin ningún intento de minimizar el número de operaciones necesarias para calcular la solución. Ejemplo: (Exponenciación). Considérese el problema de calcular xn, n entero positivo. Pot1 (real x, entero positivo n) resultado = x; for i=1 to n – 1 do resultado = resultado* x return resultado Si ƒ1(n) es el número de multiplicaciones requeridas, evidentemente para calcular xn en función de n, será ƒ1(n)= n-1 número de multiplicaciones. Es decir ƒ1(n)= θ (n). Ejemplo:(Búsqueda Exhaustiva). Buscar un producto específico en el supermercado en donde no conocemos la distribución de sus productos. Si el producto es un alimento congelado, de inmediato nos dirijimos al pasillo o sector donde se encuentran los alimentos



2

congelados, sin recorrer otro pasillo. Sin embargo, los algoritmos de Fuerza Bruta ignoran esta alternativa e ingenuamente buscan a través de todas los pasillos en el intento de encontrar el objeto o producto deseado. Ejemplo: (Problema de la máxima suma). Dada una sucesión X de números enteros. Se busca la máxima suma que se puede generar, desde un conjunto de elementos. Por ejemplo, X[0] X[1] X[2] X[3] X[4] X[5] X[6] X[7] X[8] X[9] 31 -41 59 26 -53 58 97 -93 -23 84 La suma parcial X[2] + X[3] + X[4] + X[5] + X[6] con los valores (59 + 26 – 53 + 58 + 97) = 187 soluciona el problema. Diversas otras soluciones existen sobre el particular. public static int maxSubsum1(int a[]) { /* 1 */ int maxSuma = 0; /* 2 */ for (int i = 0; i < a.length;i++) /* 3 */ for (int j = i; j < a.length; j++) { /* 4 */ int suma = 0; /* 5 */ for (int k = i; k <= j; k++) /* 6 */ suma += a[k]; /* 7 */ if (suma > maxSuma) /* 8 */ maxSuma = suma; } /* 9 */ return maxSuma; }

El análisis de tiempo de ejecución esta dado por )(11

3∑∑∑= = =

=N

i

N

ij

j

ikNO .

b) Dividir para Reinar(DpR) Digamos que un algoritmo recursivo es un algoritmo que contiene un procedimiento recursivo. La recursión es una forma poderosa, elegante y natural de resolver una amplia gama de problemas, aunque en general debemos decir que poseen una deficiencia en los tiempos de ejecución. En general, problemas de esta naturaleza pueden resolverse mediante una técnica llamada Dividir para Reinar, en la cual el problema se descompone en subproblemas del mismo tipo que el original, los que a su vez vuelven a particionarse en subproblemas hasta que este proceso genera subproblemas que se pueden resolver de manera directa. Finalmente, las soluciones entregadas por los subproblemas se combinan para obtener una solución del problema original. Cabe señalar que la técnica Dividir para Reinar resuelve un problema de tamaño n, descomponiéndolo en varios subproblemas que son similares al problema original, excepto que son de tamaño más pequeño, sin considerar si los subproblemas que se generan tras esta descomposición son los más óptimos. Es decir, la condición de "optimización" no es lo trascendente. Por otro lado, cada uno de estos subproblemas son resueltos de manera independiente y a continuación los resultados obtenidos de la resolución de cada uno de estos subproblemas se combinan para generar la solución al problema original. La resolución de un problema mediante esta técnica consta fundamentalmente de los siguientes pasos: 1. En primer lugar ha de plantearse el problema de forma que pueda ser descompuesto en k subproblemas del mismo tipo, pero de menor tamaño. Es decir, si el tamaño de la entrada es n, hemos de conseguir dividir el problema en k subproblemas (donde 1 ≤ k ≤ n), cada uno con una entrada de tamaño nk y donde 0 ≤ nk < n. A esta tarea se le conoce como división.



3

2. En segundo lugar han de resolverse independientemente todos los subproblemas, bien directamente si son elementales o bien de forma recursiva. El hecho de que el tamaño de los subproblemas sea estrictamente menor que el tamaño original del problema nos garantiza la convergencia hacia los casos elementales, también denominados casos base. 3. Por último, combinar las soluciones obtenidas en el paso anterior para construir la solución del problema original. Así se visualiza una estructura general de la técnica DpR en forma recursiva se ven así: Dado un problema P. If P es divisible en problemas más pequeños then Divide P en 2 o más partes: P1, P2, ....Pk. //Etapa Dividir Resuelve P1; Resuelve P2; ... ... Resuelve Pk; // Etapa consolidación para reinar Mezcla las k-sol. parciales en una solución para P. //combinar else Resuelve P directamente Cabe mencionar que, en general, la recursividad puede ser simulada con ayuda de iteraciones. Ahora, si bien es cierto que soluciones recursivas son fáciles de entender y de implementar, sin embargo, la desventaja más recurrente para su ejecución es la necesidad de una gran cantidad de espacio en memoria. La ventaja de los algoritmos de simplificación es que consiguen reducir el tamaño del problema en cada paso, por lo que sus tiempos de ejecución suelen ser muy buenos (normalmente de orden logarítmico o lineal). Además pueden admitir una mejora adicional, puesto que en ellos suele poder eliminarse fácilmente la recursión mediante el uso de un bucle iterativo, lo que conlleva menores tiempos de ejecución y menor complejidad espacial al no utilizar la pila de recursión, aunque va en detrimento de la legibilidad del código resultante. Respecto a la complejidad de este tipo de algoritmos señalemos que cuando un algoritmo contiene una llamada a sí mismo, el tiempo de ejecución puede ser descrito por una ecuación de recurrencia. En general si T(n) es el tiempo de ejecución de un problema de tamaño n, y lo procedemos a particionar en a-subproblemas, cada uno de los cuales es de tamaño 1/b del problema original, entonces la recurrencia queda expresada por T(n) = aT(n/b) + D(n) + C(n), en donde D(n) es el tiempo utilizado para dividir el problema en subproblemas y C(n) el tiempo para combinar la solución de los subproblemas en una solución al problema original. Ejemplo (Algoritmos de ordenamiento). Bajo esta metodología se pueden mencionar por ejemplo, InsertionSort donde la partición del archivo de tamaño n es escindido en 2 subproblemas uno de tamaño n-1 y otro de tamaño 1, generando la recurrencia T(n)= T(n-1) + n. Otro algoritmo es QuickSort, o MergeSort QuickSort(Array A, int p, int r) int q; { if (p < r) { q = Particion(A, p, r); QuickSort(A, p, q); QuickSort(A, q+1, r); } }



4

Recordar que si la etapa de particion de QuickSort toma n -1 elementos y otra con un solo elemento, el tiempo de ejecución es T(n) = T(n-1) + O(n). Dicho de otro modo si la etapa de partición n -1 comparaciones, entonces la recurrencia para expresar el número de comparaciones es C(n) = n -1 + C(a) + C(b), donde a y b son los tamaños de L1 y L2, generalmente satisfacen a+b = n -1. En el peor caso, x es el elemento mínimo en L. Entonces, a = 0 , b = n -1, y la recurrencia queda C(n)=n -1 + C(n -1) = O(n2). Así podrá ver, que también existe un caso peor que lo deja en igualdad de condiciones con InsertionSort. Pero si la partición genera dos regiones de tamaño n/2 QuickSort mejora en forma substancial, pues la recurrencia es T(n) = 2T(n/2) + O(n), cuya solución es O(nlogn). También existen situaciones en donde pueden balancearse, es decir recurrencias del tipo T(n) = T(9n/10) + T(n/10) + n, pero que no generan cambios substanciales respecto a la anterior. Otro algoritmo es en donde la partición del archivo de tamaño n se escinde en dos partes iguales, llamado MergeSort MergeSort(Lista L) { if (longitud(L) < 2) return L else { particiona L en listas L1 y L2, con n/2 elementos L1 = mergeSort(L1) L2 = mergeSort(L2) return merge(L1,L2) } } la que genera una recurrencia del tipo T(n)=T( piso(n/2) + T(techo(n/2)), cuya resolución se interpreta como la complejidad del algoritmo. Ejemplo: (Problema de la máxima suma). Retomamos el problema de la suma máxima, usando esta vez una estrategia DpR que representa una solución algorítmica general. En efecto, Dividir: Particionar el problema de tamaño N en (al menos) 2 subproblemas, cuando N > 1 , sino solucionar directamente el problema de tamaño 1. Reinar: Solucionar los subproblemas de la misma forma. Combinar: Combinar las soluciones parciales. a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] 4 -3 5 -2 -1 2 6 -2 1. Mitad 2. Mitad La suma más grande en la primera mitad es 6 (a[0] + a[1] + a[2]), la suma más grande en la segunda mitad es 8 (a[5] + a[6]). La suma maximal en la 1. Mitad, en la cual es considerado el último elemento de la 1. Mitad inclusive, es decir (a[0] + a[1] + a[2] + a[3]) es 4. La suma maximal en la 2. Mitad, en la cual se considera el primer elemento de la 2. Mitad es 7. La suma maximal que abarca ambas mitades es 4 + 7 = 11. private static int maxSucSum(int a[], int izq, int der) { /* 1 */ if (izq == der) /* 2 */ if (a[izq] > 0) // Caso que este elemento sea positivo



5

/* 3 */ return a[izq]; // luego este es el max.Suma parcial /* 4 */ else return 0; /* 5 */ int mitad = (izq + der) / 2; /* 6 */ int maxIzqSuma = maxSucSum(a, izq, mitad); /* 7 */ int maxDerSuma = maxSucSum(a, mitad + 1, der); /* 8 */ int maxLimiteIzqSuma = 0, limiteIzqSuma = 0; /* 9 */ for (int i = mitad; i >= izq; i--) { /*10 */ limiteIzqSuma += a[i]; /*11 */ if (limiteIzqSuma > maxLimiteIzqSuma) /*12 */ maxLimiteIzqSuma = limiteIzqSuma; } /*13 */ int maxLimiteDerSuma = 0, limiteDerSuma = 0; /*14 */ for (int i = mitad + 1; i <= der; i++) { /*15 */ limiteDerSuma += a[i]; /*16 */ if (limiteDerSuma > maxLimiteDerSuma) /*17 */ maxLimiteDerSuma = limiteDerSuma; } /*18 */ if (maxIzqSuma > maxDerSuma) if (maxIzqSuma > (maxLimiteDerSuma + maxLimiteIzqSuma)) return maxIzqSuma; else return (maxLimiteDerSuma + maxLimiteIzqSuma); else if (maxDerSuma > (maxLimiteDerSuma + maxLimiteIzqSuma) ) return maxDerSuma; else return (maxLimiteDerSuma + maxLimiteIzqSuma); } public static int maxSucSum3(int a[]) { return maxSucSum(a, 0, a.length - 1); } La implementación toma un tiempo O(NlogN). Ejemplo: (Búsqueda Binaria). Dado un número X y una sucesión de números enteros A0, A1, A2, ... , AN-1 en memoria. Se pide hallar la posición i tal que Ai=X , y por otro lado devuelve i=-1 si X no fue encontrado. public static int Bbin(Comparable a[], Comparable x) { /* 1 */ int izq = 0, der = a.length - 1; /* 2 */ while (izq < der) { /* 3 */ int mitad = (izq + der) / 2; /* 4 */ if (a[mitad].compareTo(x) < 0) /* 5 */ izq = mitad + 1; /* 6 */ else if (a[mitad].compareTo(x) > 0) /* 7 */ der = mitad - 1; else /* 8 */ return mitad; // hallado } /* 9 */ return -1; // No hallado } Podemos ver que la línea 2 es decisiva en la búsqueda del elemento. Comienza con (der – izq) = N-1 y termina con (der – izq) = -1. Junto a cada pasada por el ciclo se debe particionar en mitad(der – izq). Si (der – izq) = 128, luego los valores maximales según cada iteración es: 64, 32, 16, 8, 4, 2, 1, 0, -1. El tiempo de ejecucuón es O(logN), como se puede ver tras la resolución de la ecuación de recurrencia



6

T(n) = 1 T( n/2) + θ(1) ⇓ ⇓ ⇓ # subproblemas tamaño del subproblema dividir & combinar La búsqueda Binaria es la implementación de un Algoritmo para una estructura de datos (de almacenamiento secuencial Lista, Array). Para la búsqueda de algún elemento necesita de tiempo O(logN). Toda otra operación (p.e. Agregar) necesita tiempo O(N). Ejemplo: Podemos plantearnos también diseñar un algoritmo de búsqueda “ternaria”, que primero compara con el elemento en posición n/3 del vector, si éste es menor que el elemento x a buscar entonces compara con el elemento en posición 2n/3, y si no coincide con x busca recursivamente en el correspondiente subvector de tamaño 1/3 del original. ¿Conseguimos así un algoritmo mejor que el de búsqueda binaria?. Ejemplo: (Exponenciación). Retomando el problema, pero con un enfoque recursivo alternativo a Pot1(), en tal caso se piensa si xn puede ser calculado obteniendo el cuadrado de

n/2x y a continuación multiplicando el resultado por x si n es impar. Es decir: xn = n/2n/2 xx . x , si n impar, ó xn = n/2n/2 xx , si n par. Si en particular se usa Pot1() para

calcular n/2x se tendrán n/2 multiplicaciones. Luego para completar el cálculo de xn, se requiere o bien una, o bien dos multiplicaciones adicionales dependiendo si n es par o impar. De este modo, simplemente calculando n/2 y usando este resultado para calcular xn, tenemos un medio efectivo para reducir aproximadamente a la mitad el número de multiplicaciones requeridas para calcular xn. Sin embargo, utilizando esta misma alternativa podría ser posible de calcular n/2x . En concreto, Pot1() puede usarse para calcular x

2n/2 ,

y este resultado se eleva al cuadrado (y se multiplica por x si n/2 es impar) para formar xn/2, y así sucesivamente generando el algoritmo. Pot2 ( real x, entero positivo n) if n = 1 then return x y = Pot2 (x, n/2) if n es impar then return y · y · x else return y · y Sabemos que en el mejor caso, cuando n = 2k , Pot2( ) realiza k–multiplicaciones, de donde k = log2(n). En general, θ(log n) - número de multiplicaciones. Ejemplo.(multiplicación de enteros grandes). Considerar el producto de dos enteros X e Y de n-bits. Recordar que el algoritmo que Ud. conoce de la escuela, bien podría considerarse de fuerza bruta, dado que el costo es O(n2), si se toman las multiplicaciones y las adiciones de un solo bit o dígito como un paso. Una estrategia DpR considera dividir X e Y en dos enteros de n/2 bits cada uno. X = B + A2n/2 Y = D + C2n/2 A lo que el producto XY puede escribirse como XY = BD + AC2n + (AD + BC)2n/2



7

Realizando 4-multiplicaciones de enteros de n/2 - bits (AC, AD, BC, BD), 3-sumas de enteros con un máximo de 2n-bits. Generando una recurrencia T(1) = 1. T(n) = 4T(n/2) + cn, cuya resolución es del orden O(n2) no mejor a la que aprendió en la escuela. Sin embargo si ahora se hacen los cambios XY = BD + AC2n + [(A - B)(D - C) + AC + BD]2n/2

Aunque parezca más complicado, sólo requiere 3-multiplicaciones de enteros con n/2-bits, AC, BD y (A - B)(D - C), generando la recurrencia T(1) = 1. T(n) = 3T(n/2) + cn, cuya solución es aproximadamente O(n1.5849625), mejorando substancialmente la performance de lo aprendido en la escuela. Por ejemplo, con X= 31785=124* 256 + 41, donde a=124, b=41 Y= 29846=116*256 + 150, donde c=116, d=150. Obteniendo el siguiente producto ac= 14384, bd= 6150, (a + b)(c + d) – ac – bd = 23356. Ejemplo(Multiplicación de Matrices). Multiplicar A por B genera una matriz C todas ellas de orden n x n. De donde el tiempo para computar C es del orden n3. En donde n2 son los coeficientes cij de C y n para calcular todos los cij. Este es el algoritmo básico que Ud. conoce. Sin embargo la matriz anterior se puede pensar como una matriz n x n = 2 x 2 matrices de n/2 x n/2 submatrices a saber C = A x B, es decir r s a b e g = x t u c d f h con esto podemos decir que r = ae + bf, s = ag + bh, t = ce + df, u = cg + dh de donde una multiplicación en una matriz n x n es "reducida" a 4-ecuaciones, de las cuales se necesitan 2-multiplicaciones de dos n/2 x n/2 matrices, 1- suma de dos n/2 x n/2 matrices, dando en total 8-Multiplicaciones y 4- adiciones. T(n) = 8 T( n/2) + θ( n2 ) ⇓ ⇓ ⇓ # subproblemas tamaño del subproblema dividir & combinar no lográndose una mejora, pues la solución es de orden n3. Sin embargo, Strassen propuso la idea de multiplicar 2 x 2 matrices con solamente 7- multiplicaciones( en vez de 8), lo hizo considerando P1 = a ( g - h ) P2 = ( a + b ) h P3 = ( c + d ) e P4 = d ( f - e )



8

P5 = ( a + d ) ( e + h) P6 = ( b - d ) ( f + h) P7 = ( a - c ) ( e + g), en donde r = P5 + P4 - P2 + P6 s = P1 + P2 t = P3 + P4 u = P5 + P1 - P3 - P7. Según este principio se necesitan 7-multiplicaciones y 18 adiciones o restas. T(n) = 7 T( n/2) + θ( n2 ) ⇓ ⇓ ⇓ # multiplicaciones tamaño del subproblema dividir & combinar cuya solución es θ( n2.81).(teo. Maestro), de manera que θ(n2.81) v/s θ( n3) gana para n>=50 en la practica. c) Programación Dinámica Un algoritmo de programación dinámica almacena los resultados, o soluciones de subproblemas más pequeños y posteriormente los consulta en lugar de volver a calcularlos, para cuando los necesita para resolver subproblemas más grandes. De manera que PD es idónea para problemas en los que un algoritmo recursivoresolvería muchos de los subproblemas varias veces. En general la idea es convertir una solución recursiva en un algoritmo de programación dinámica. La esencia de los algoritmos de programación dinámica es que cambian espacio por rapidez almacenando soluciones a subproblemas en lugar de volver a resolverlos. En general, la programacion dinamica debe su nombre al siguiente tipo de problema. Un proceso es examinado al principio de cada uno de N periodos sucesivos. Del examen resulta un valor x que es una (o más) variable que sirve para juzgar la situacion del proceso. Sea (k,x) el dato correspondiente al periodo k. En base a esta informacion elegimos una accion correctiva d tomada de un conjunto D(k,x). Esto provoca una transicion a (k+1,x′ ) donde x′ = T(k,x,d) con un costo de la trancisión c(k,x,d). Se plantea el problema de determinar las acciones correctivas en cada una de los N periodos de forma que la suma de los costos de los N periodos sea mínimo. Algunas observaciones que debe tener en cuenta son: • Atacar el problema de “arriba hacia abajo” como si fuera a desarrollar un algoritmo

recursivo; determinamos cómo resolver un problema grande suponiendo que conocemos soluciones para problemas más pequeños.

• Guardando los resultados de los problemas pequeños podremos evitar cálculos repetidos. • Decidir que estructura de dato es la más apropiada, en muchos casos lo mejor es un array

uni o bidimensional. • Determinar finalmente como obtener la solución del problema a partir de los datos Los coeficientes binomiales se prestan en forma ideal para aplicar lo antes visto. Sabemos que los coeficientes binomiales se pueden definir con la ecuación de recurrencia C(n, k)= C(n -1, k -1) + C(n – 1, k) , para n > 0 y k > 0. C(n, 0)= 1, si n ≥ 0. C(0, k) = 0, si k > 0.



9

En donde, C(n, k) también se puede interpretar como el número de formas en que podemos escoger k objetos distintos de un conjunto de n objetos. En este primer programa se muestra la función sugerida por la relación de recurrencia dada para C(n,k). /* Calculo de Binomio(m, n) usando una metodología dividir para Reinar. */ public class BinomialDpR { static int[][] llamadas; static int Binom(int m, int n) { if (n == 0) return 1; else if (m == 0) return 0; else return Binom(m-1, n) + Binom(m-1, n-1); } public static void main (String[] args) { llamadas = new int[31][16]; System.out.println(Binom(30, 15)); System.out.println(llamadas[0][7]); for (int i = 0; i<1 ; i++) { for (int j = 0; j<11 ; j++) System.out.print(llamadas[i][j] + " "); System.out.println(); } } } En este programa BinomCache muestra la implementación de C(n,k) como un algoritmo de programación dinámica. public class BinomCache { static int[][] cache; private static int escogerCache (int m, int n) { if (cache[m][n] == -1) { int resp; if (n == 0) resp = 1; else if (m == 0) resp = 0; else resp = escogerCache(m-1, n) + escogerCache(m-1, n-1); cache[m][n] = resp; } return cache[m][n]; } public static int escoger (int m, int n) { cache = new int[m+1][n+1]; for (int i=0; i<m+1; i++) for (int j=0; j<n+1; j++) cache[i][j] = -1; return escogerCache(m, n); }



10

public static void main (String[] args) { System.out.println(escoger(30, 15)); } } Ud. podrá ver a simple vista la rapidez de este último al compararlo con el primero. Otro ejemplo clasico es el problema del orden de multiplicación de matrices, que es uno de los ejemplos clásicos dentro de la Programación dinámica. El propósito no es tan solo mostrar la forma de resolver el problema del orden de la multiplicación de matrices, sino más bien como aplicar los principios de desarrollo de un algoritmo de Programación Dinámica. Comencemos por definir una Matriz A de orden n × m, la que está compuesta por elementos a i, j , dispuestos en un arreglo, con n-filas y m-columnas a 1, 1 a 1, 2 ....... a 1, m a 2, 1 a 2, 2 ....... a 2, m A = a 3, 1 a 3, 2 ....... a 3, m ... . .. a n,1 a n,2 ......... a n,m

Dada una matriz A de orden p × q , y una matriz B de orden q × r. La multiplicación A × B es una matriz C de orden p × r, dada por c i, j = q ∑ a i, k × b k,j k=0

para 1 ≤ i ≤ p, y 1 ≤ j ≤ r. Observaciones. Si AB esta definida puede que BA no este definida, puede ocurrir que AB ≠ BA, Recursivamente definimos el producto A1 A2 A3 A4 A5 ..... As-1 As como A1 (A2 (A3 (A4 (A5 ..... (As-1 As))). La multiplicación de matrices es asociativa, es decir, A1 A2 A3 = (A1 A2 )A3 = A1 (A2 A3 ). La complejidad de la multiplicación de matrices es del orden O(pqr). Notar que C tiene pr – entradas y toda entrada toma tiempo O(q). Dada A de orden p × q , B de orden q × r, y una matriz C de orden r × s, entonces D puede ser calculada en dos sentidos, A(BC), o (AB)C. Entonces el número de multiplicaciones necesarias es : Mult [(AB)C] = p × q × r + p × r × s, Mult [A(BC)] = q × r × s + p × q × s, si ahora p= 5, q=4, r= 6 y s=2, entonces Mult [(AB)C] = 180, Mult [A(BC)] = 88, muestran , según sea el caso una gran diferencia. Por lo tanto la sucesión de multiplicaciones es de suma importancia.



11

Problema: Dada una sucesión de matrices A1 , A2 , A3 , A4 .. An y dimensiones p0, p1, p2, p3,...., pn , en donde Ai es de dimensión pi-1 × pi, donde 1 ≤ i ≤ n. Determinar la sucesión de multiplicaciones que minimiza el número de multiplicaciones. Es decir, en otras palabras, ¿Cómo deberemos calcular A1 × A2 × A3 × A4 ×..× An y cuál es el costo mínimo de hacerlo?. Notar que si se tienen matrices M= A1 × A2 × A3 × A4 de orden 10 × 20, 20 × 50, 50 × 1, 1 × 100, evaluando M en el orden A1 × (A2 × (A3 × A4 )) requiere 125.000 operaciones, mientras que (A1 × (A2 × A3)) × A4 requiere solamente 2.200 operaciones, de manera que la optimización de la sucesión de parentización es de suma importancia y bien vale considerarla. Sea T(n) las formas distintas de parentizar n-matrices, en el caso para M se tenía T(4)=5, en donde se mostraron dos de las 5-posibilidades. En general se tiene n -2 T(n) = ∑ T(i) × T(n – i), para n > 1. i=1 En efecto, sean las matrices A1 , A2 , A3 , A4 .. An y la última multiplicación realizada es T(i)= (A1 A2 A3 A4 .. Ai ) × (Ai+1Ai+2 Ai+3 .. An ) = T(n-i) , de manera que existen T(i) × T(n – i) formas de calcular el producto para cada i posible. La solución de esta recurrencia esta dada por T(n-1) = 1/(n-1)Comb(2n, n), que es el número de Catalan cuyo resultado es de orden exponencial. Desarrollando una propuesta en Programación Dinámica. Etapa 1: Determinar la estructura de una solución optimal, (en este caso una parentización optimal). Descomponer el problema en subproblemas: Para cada par 1 ≤ i ≤ j ≤ n, determinar la sucesión de multiplicaciones para A i...j = AiAi+1 .. Aj que minimiza el número de multiplicaciones. Claramente Ai...j =AiAi+1 .. Aj es una matriz pi-1 × pj, Problema Original: Determinar la sucesión de multiplicaciones para A1....n. Parentización de alto nivel para Ai...j, para cualquier sucesión de multiplicaciones optimal se encontrara que en la última etapa se debe realizar el producto de dos matrices Ai...k y Ak+1...j, para algún k esto es: Ai .. j = (AiAi+1 .. Ak ) (Ak+1 .. Aj ) = (Ai .. k ) (Ak+1.. j ) esto se interpreta en forma particular como A3 .. 6 = (A3 (A4 A5 )) (A6 ) = (A3 .. 5 ) (A6.. 6 ), donde k=5 entonces el problema de determinar la sucesión de multiplicaciones optimal es cuestionada en términos a considerar ¿Cómo decido donde particionar la cadena o sucesión, es decir quién es k?. (debemos buscar entre todos los posibles....valores de k.) ¿Cómo parentizar las subcadenas (Ai .. k ) (Ak+1.. j )? (debemos aplicar el mismo procedimiento en forma recursiva). Principio de Optimización



12

Notar que este problema satisface el principio de Optimización, pues si queremos encontrar la sucesión de multiplicaciones optimal Ai .. j debemos usar la sucesión optimal para (A i .. k ) y para (A k+1.. j ), en otras palabras los subproblemas deben ser resueltos en forma optimal para que el problema global sea resuelto en forma optimal. Etapa2: Recursivamente definimos el valor de una solución optimal. En este sentido, almacenamos las soluciones de los subproblemas en una tabla, en donde para cada par 1 ≤ i ≤ j ≤ n, m[i, j] denota el número mínimo de multiplicaciones necesarias para computar Ai .. j. El costo optimal puede ser expresado por la siguiente definición recursiva. Recursivamente definimos el valor de una solución optimal, en donde m[i, j] = 0, si i=j ó m[i, j] = Minimo 1 ≤ k < j ( m[i, k] + m[k+1, j] + pi-1 pk pj ) , si i < j. Algoritmo Para computar el costo mínimo en multiplicar n-matrices A1A2 A3A4 .. An . Input: p0, p1, p2, p3,...., pn , donde pi-1 y pi son las dimensiones de Ai. Output: Costo mínimo de multiplicar las matrices Ai asumiendo que p1p2p3 operaciones se necesitan para multiplicar una matriz p1p2, por una matriz p2p3. Cadena_Matriz(p, n) { for i=1 to n do Ai i=0; for l = 2 to n do { for i=1 to n - l + 1 do { j = i + l –1; m[ i, j ] = ∞; for k = i to j – 1 do { q = m[ i, k ] + m[ k+1, j ] + pi-1 pk pj ; if ( q < m[i, j] ) { m[i, j] = q; s[i, j] = k; } } } } return m y s ; (Optimo en m[1, n]) } La complejidad del algoritmo a raíz de los tres loops anidados, con valores de los indices menores que n, origina que sea de complejidad O(n3), mientras que el espacio de complejidad es Θ (n 2). Ejemplo: Dada una cadena n = 4 matrices A1 , A2 , A3 , A4 con p0 = 5, p1 = 4, p2 = 6, p3 = 2 y p4 = 7. Hallar m[1, 4]. Inicialización aparece representada por la Fig. 1



13

Fig. 1 Fig. 2 En Fig. 2, computamos m[1, 2], que por definición está dado por: m[1, 2] = Mínimo 1 ≤ k < 2 ( m[1, k] + m[k+1, 2] + p0 pk p2 ) , si i < j. = m[1, 1] + m[2, 2] + p0 p1 p2 = 120. En Fig. 3, se obtiene m[2, 3], y en Fig. 4, se obtiene m[3, 4], por los cálculos.

Fig. 3 Fig. 4 m[2, 3] = Mínimo 2 ≤ k < 3 ( m[2, k] + m[k+1, 3] + p1 pk p3 ) , si i < j. = m[2,2] + m[3, 3] + p1 p2 p3 = 48. m[3, 4] = Mínimo 3 ≤ k < 4 ( m[3, k] + m[k+1, 4] + p2 pk p4 ) , si i < j. = m[3, 3] + m[4, 4] + p2 p3 p4 = 84. Análogamente se van completando los elementos faltantes de la Tabla.



14

m[1, 3] = Mínimo 1 ≤ k < 3 ( m[1, k] + m[k+1, 3] + p0 pk p3 ) , si i < j. = Mínimo entre m[1, 1] + m[2, 3] + p0 p1 p3 y m[1, 2] + m[3, 3] + p0 p2 p3 = 88. m[2, 4] = Mínimo 2 ≤ k < 4 ( m[2, k] + m[k+1, 4] + p1 pk p4 ) , si i < j. = Mínimo entre m[2, 2] + m[3, 4] + p1 p2 p4 y m[2,3] + m[4,4] + p1 p3 p4 =104. Tal como lo muestran las Fig. 5 y 6 respectivamente.

Fig. 5 Fig. 6 Obteniendo finalmente la Fig. 7, la que termina de calcular m[1,4]. El cual se obtiene, a través de los siguientes cálculos: m[1, 4] = Mínimo 1 ≤ k < 4 ( m[1, k] + m[k+1, 4] + p0 pk p4 ) , si i < j. = Mínimo entre m[1,1] + m[2, 4] + p0 p1 p4 m[1,2] + m[3,4] + p0 p2 p4 m[1,3] + m[4,4] + p0 p3 p4 =158.

Fig. 7



15

La idea es mantener un array s[1.. n, 1.. n], donde s[ i, j ] denota k para la partición optima en los cálculos de Ai .. j = Ai .. k Ak+1.. j . El array s[1.. n, 1.. n], puede ser usado recursivamente para recubrir la sucesión de multiplicaciones. Cómo recubrir la sucesión de multiplicaciones.? s[1, n] corresponde (A1 .. As[1,n] ) (As[1,n]+1 .. An ) s[1, s[1, n]] corresponde (A1 .. As[1, s[1,n]] ) (As[1, s[1,n]] +1 .. As[1,n] ) s[s[1, n] + 1, n]..... y así sucesivamente. Se construye una solución optimal a partir de la información calculada. El código actual de multiplicación usa el valor s[i, j] para determinar como particionar o escindir la sucesión actual. Asumamos que las matrices son almacenadas en un array de matrices A[1..n], y que s[i, j] es global para este procedimiento recursivo. El siguiente procedimiento recursivo entrega la cadena de un producto matricial A i .. j dada por las matrices A1 , A2 , A3 , A4 .. An , la tabla s computada por Cadena_Matriz(p, n) y los indices i, j. La llamada inicial a este procedimiento se hace a través de Mult(A, s, 1, n). Mult(A, s, i, j) if j > i then X= Mult(A, s, i, s[i, j] ) // X = A i .. k donde k = s[i, j] Y= Mult(A, s, s[i, j] + 1, j) // Y = A k+1 .. j return Mult_Matrices_Usual(X, Y) else return Ai Veamos ahora cómo encontrar la sucesión de multiplicaciones optimal. Supongamos que las tablas m y s ya fueron computadas por el procedimiento Cadena_Matriz(p, n) para n = 6 y las siguientes dimensiones. A1 de dimensión 30 × 35, A2 de dimensión 35 × 15, A3 de dimensión 15 × 5, A4 de dimensión 5 × 10, A5 de dimensión 10 × 20 y A6 de dimensión 20 × 25. Tal como se muestra en Fig. 8.

Fig. 8 Consideremos n=6, y computemos A 1 .. 6 , asumiendo que el array computado es s[1..6,1..6] y de donde la sucesión de multiplicaciones corresponden a Mult(A, s, 1, 6 ) s[1, 6] = 3 y que corresponde a (A1 A 2 A3 ) (A4 A 5 A6 ) Mult(A, s, 1, 3 ) s[1, 3] = 1 “ (A1 (A 2 A3 )) Mult(A, s, 4, 6 ) s[4, 6] = 5 “ ((A4 A 5 )A6 ) Mult(A, s, 2, 3 ) s[2, 3] = 2 “ (A 2 )(A3) Mult(A, s, 4, 5 ) s[4, 5] = 4 “ (A 4 ) (A5) de aquí entonces que la sucesión de multiplicaciones final es (A1 ((A 2 ) ( A3 ))) (((A4 ) (A 5 ))A6 )



16

Otra forma de representarlo es a través de un Arbol de expresión aritmética, tal como se visualiza a continuación, en donde cada nodo se identifica con un subproblema y representa una matriz o bien una multiplicación a efectuar. Cada invocación de Mult(A, s, i, j), visita un nuevo nodo del árbol de expresión, que posee 2n – 1 nodos, así que existen 2n – 1 invocaciones, y Mult(A, s, i, j), tarda un tiempo Θ(n). (1,6) * (1,3) (4,6) * * (2,3) (4,5) A1 * * A6 A2 A3 A4 A5 Ejemplo Matriz dimension r pr A1 10*20 0 10 A2 20*3 1 20 A3 3*5 2 3 A4 5*30 3 5 4 30 1 2 3 4 1 0 600 750 1950 2 0 300 2250 3 0 450 4 0 Construcción de la solución optimal desde la información computada Ejemplo Matriz dimension r pr A1 10*20 0 10 A2 20*3 1 20 A3 3*5 2 3 A4 5*30 3 5 4 30 1 2 3 4 1 A1 A1A2 (A1A2)A3 (A1A2)(A3A4) 2 A2 A2A3 A2(A3A4) 3 A3 A3A4 4 A4



17

Implementación Archivo MultMatPD.java /* Esta es una solución programación dinámica para determinar el orden optimal de una sucesión de matrices. Los argumentos en la línea de comando son p0, p1, p2,..., pn, donde las matrices que deseamos multiplicar y tienen dimensiones (p0 x p1), (p1 x p2),..., (p(n-1) x pn) y en este orden. Ejemplo de uso: >java MultMatPD 30 35 15 5 10 20 25 A1 (30 * 35) A2 (35 * 15) A3 (15 * 5) A4 (5 * 10) A5 (10 * 20) A6 (20 * 25) Izq_a_Der costo:40.500 Producto Minimo costo: 15.125 Parentización Optimal: ( (A1 )( (A 2 )(A3 )))(((A4 )(A 5 ))(A6)) */ public class MultMatPD { public static void main(String args[]) { int n; // numero de matrices int[] dim; // n-ésima matriz (n>0)tiene dim[n-1] filas y dim[n] columnas int[][] opt_cost; // opt_cost[i,j] es el costo optimal de multiplicar // la i-ésima con la j-ésima matriz (inclusive) int[][] partic; // partic[i,j] = k cuando la multiplicación final en un //producto optimal de Ai...Aj es (Ai...Ak)(A(k+1)...Aj) int length, partida_pos, fin_pos, cost, actual_min, izqder_costo, i; // crear arrays y leer las dimensiones de las matrices n = args.length - 1; dim = new int[n+1]; opt_cost = new int[n+1][n+1]; partic = new int[n+1][n+1]; //ingreso por teclado for (i = 0; i<= n; i++) dim[i] = Integer.parseInt(args[i]); // no existe costo para multiplicar una matriz single for (i=1; i <= n; i++) opt_cost[i][i] = 0; // computa los costos optimales para substrings de longitud 2,3,...,n for (length=2; length <= n; length++) { for (partida_pos=1; partida_pos <= n - length + 1; partida_pos++) { fin_pos = partida_pos + length - 1; // chequear todas los posibles puntos de particiones en el substring for (i=partida_pos; i<fin_pos; i++) { cost = opt_cost[partida_pos][i] + opt_cost[i+1][fin_pos] + dim[partida_pos - 1] * dim[i] * dim[fin_pos]; actual_min = opt_cost[partida_pos][fin_pos];



18

if (actual_min == 0 || cost < actual_min) { // ya que el costo es siempre estrictamente positivo, sabemos // que si opt_cost[i,j]==0, no ha sido asignado por ahora. // Asi, testeamos para cero en vez de necesitar un valor // de "infinito". opt_cost[partida_pos][fin_pos] = cost; partic[partida_pos][fin_pos] = i; } } } } // print la lista de las matrices y sus dimensiones for (i= 1; i <= n; i++) System.out.println("A"+i+"\t"+"("+dim[i-1]+","+dim[i]+")"); // print los costos de calcular el producto // mult. los costos de izq_a_der p0.p1.p2 + p0.p2.p3 +...+ p0.p(n-1).pn izqder_costo = 0; for (i=1; i<n; i++) { izqder_costo += dim[i]*dim[i+1]; } izqder_costo *= dim[0]; System.out.println ("Izq_a_Der, costo : " + izqder_costo); System.out.println ("Minimo producto, costo: "+opt_cost[1][n]); //print en parentesis, el producto optimal System.out.print ("Parentizacion Optimal : "); printParentizar(1, n, partic); System.out.println(); } private static void printParentizar(int partida_pos, int fin_pos, int[][] particion) { int partic_pos; if (partida_pos == fin_pos) System.out.print("A"+partida_pos); else { partic_pos = particion[partida_pos][fin_pos]; System.out.print("("); printParentizar(partida_pos, partic_pos, particion); System.out.print(")("); printParentizar(partic_pos + 1, fin_pos, particion); System.out.print(")"); } } } Aqui aparece con un MVC asociado.



19

String Matching (búsqueda en texto) Otro ejemplo de aplicación de la Programación Dinámica es String Matching. El problema “string matching” se formaliza como sigue. Consideremos que un texto es un array T[1..n] de longitud n y que los pattern o “formas” es un array P[1..m] de longitud m. Se supone que los elementos de P y T son caracteres extraídos de un alfabeto finito. El array de caracteres de P y T son a menudos llamados string de caracteres. Algoritmos String Matching son frecuentemente utilizados para la búsqueda de formas particulares en las sucesiones de ADN. Ejemplo: El objetivo es encontrar todas las ocurrencias del pattern P = abaa en el texto T = abcabaabcabac. Tal como se ve en Fig. 1 el pattern ocurre solamente una vez en el texto. En este caso todo carácter del pattern esta conectado por una línea vertical y ensombrecido para caracterizar los efectos del matching.



20

Una implementación “naive” es la que se propone, pero muy simple de implementar, la cual se basa en encontrar todos los “shifts” válidos usando un loop que va chequeando las condiciones P[1 ..m] = T[s+1..s+m] para toda de las n – m + 1 posibles valores de s. Naive-String-Matcher(T, P) n=long[T]; m= long[P] for s=0 to n-m do if P[1..m] = T[s+1..s+m] then print “pattern ocurrió en la posición” s. Implementación del algoritmo y ejecución del ejemplo, considerando que el texto T= abcabaabcabac y el pattern P= abaa, entregando como resultado posición=3 public class KMP_Naive { static int n = 1; private static int[] iniSig (String pattern) { int[] siguiente = new int [pattern.length ()]; int i = 0, j = -1; siguiente[0] = -1; while (i < pattern.length () - 1) { while (j >= 0 && pattern.charAt (i) != pattern.charAt (j)) j = siguiente[j]; i++; j++; siguiente[i] = j; } return siguiente; } public static int kmp_Busca(String texto, String pattern) { int[] siguiente = iniSig (pattern); int i = 0, j = 0; n = 1; while (i < texto.length ()) { while (j >= 0 && pattern.charAt (j) != texto.charAt (i)) { j = siguiente[j]; } i++; j++; if (j == pattern.length ()) return i - pattern.length (); } return -1; } public static void main (String[] args) { String p = "abaa";//pattern P int[] siguiente = iniSig(p); for (int i = 0; i < siguiente.length; i++) System.out.println ("siguiente[" + i + "] = " + siguiente[i]); System.out.println ("posicion = " + kmp_Busca("abcabaabcabac", p)); } } Ahora si el pattern P es relativamente grande y el alfabeto de donde se extraen los caracteres es razonablemente grande entonces el algoritmo de Boyer-Moore es más eficiente para string matching.



21

Dentro de este contexto se encuentran una serie de problemas, entre ellos el hallar la subsecuencia común más larga entre 2 string, conocido como “Longest Common Subsequence”, en adelante (LCS). Este es otro ejemplo clásico de la técnica de programación dinámica. Antes de que definamos el problema general de la subsecuencia común más largo, empezamos con un pequeño ejemplo. Suponga que se da un string (como modelo) y un string más largo (como texto). La idea es saber si los caracteres del modelo aparecen en orden (pero posiblemente separado) dentro del texto. Si ello ocurre, decimos que el modelo es una subsecuencia del texto, y si es la subsecuencia más grande por ejemplo "nomi" es una subsecuencia de "conocimiento" como solución al problema. Formalmente, digamos que una sucesión X = < x1 , x2 , ....., xm > y otra sucesión Z =< z1 , z2 , ....., zk > es una subsucesión de X si existe una sucesión de índices estrictamente creciente i1 , i2 , ....., ik de índices de k, tal que para todo j=1, 2, 3..., k, se tiene x i j = z j. Por ejemplo, Z=<B, C, D, B> es una subsucesión de X= <A, B, C, B, D, A, B>, con subíndices <2, 3, 5, 7>. Dadas dos secuencias X e Y, se dice que una sucesión Z es una subsucesión común de X e Y si Z es una subsucesión de ambas , es decir de X e Y. Por ejemplo, si X= <A, B, C, B, D, A, B> , Y= < B, D, C, A, B, A> entonces la sucesión <B, C, A> es una subsucesión común de X e Y. Observar que <B, C, A> no es la más larga de X e Y, pues <B, C, B, A> es también común a ambas y tiene longitud 4. Notar que tampoco es única, pues la sucesión <B, D, A, B> también lo es. Sin embargo, no existe LCS de longitud 5 o mayor. ¿Por qué podríamos querer nosotros resolver el problema de la subsecuencia común más larga? Hay varias aplicaciones que motivan este estudio. * En la biología molecular. Sucesiones de ADN (genes) pueden representarse como sucesiones de cuatro elementos básicos ACGT que se corresponden a las cuatro submoleculas que forman el ADN. Cuando los biólogos encuentran una nueva sucesión, ellos quieren saber qué otras sucesiones son similares a ella. De allí que la computación de las dos sucesiones similares pasan por encontrar la longitud de su subsecuencia común más largo. * Comparación de archivos. En Unix-Linux comandos "diff" se usan para comparar dos versiones diferentes del mismo archivo, para determinar qué cambios se han hecho al archivo. Funciona encontrando una subsecuencia común más larga de las líneas de los dos archivos; en donde cualquier línea en la subsecuencia no se ha cambiado. En este caso debemos pensar que cada línea de un archivo es un carácter dentro de un string. Un approach “fuerza bruta” para resolver LCS es enumerar todas las subsecuencias de X y chequearlas todas ellas para ver si es también subsecuencia de Y, hasta encontrar la subsecuencia más larga. Estas observaciones nos dan un algoritmo recursivo altamente ineficiente, pues recordar que toda subsecuencia de X corresponde a un subconjunto de los índices {1, 2, 3,..., m} de X, existiendo 2m subsucesiones de X, de manera que el tiempo es exponencial, haciéndolo impracticable para sucesiones más largas. Basado en Teorema 16.1 pág. 315 (CLR) podemos admitir una subestructura optimal de un LCS, y en este contexto al igual que en el problema de Parentización de Matrices se establece una recurrencia para el costo de una solución optimal. Se define c[i,j] como la longitud de un LCS de secuencias Xi , Yj. Si i=0 o j=0 una de las sucesiones tiene longitud 0, así LCS tiene longitud 0. La subestructura optimal de LCS está dada por la formula recursiva:



22

≠>−−=>+−−==

=

ii

ii

yxyjijicjicmaxyxyjijic

joijic

0,]),1[],1,[(0,1]1,1[

000],[

Basada en estas ecuaciones podríamos escribir un procedimiento recursivo para computar la longitud de un LCS de 2 secuencia, pues existen solamente O(mn problemas distintos. int lcs_long(char * A, char * B) { if (*A == ' \0 ' || *B == ' \0 ') return 0; else if (*A == *B) return 1 + lcs_long(A+1, B+1); else return max(lcs_long(A+1,B), lcs_long(A,B+1)); } Sin embargo, el objetivo es usar Programación Dinámica. El procedimiento considera 2 sucesiones X = < x1 , x2 , ....., xm > e Y =< y1 , y2 , ....., yn > como entrada, se procede a almacenar los valores c[i,j], en una tabla c[0..m, 0..n] cuyas entradas son computadas primera fila de c es llenada de izq. a der., luego la segunda fila, y así sucesivamente. Al mismo tiempo se mantiene una tabla b[1..m, 1..n] para simplificar la construcción de una solución optimal. LCS-Long(X, Y) m= long[X] n= long[Y] for i=1 to m do c[i,0]=0 for j=1 to n do c[0, j]=0 for i=1 to m do for j=1 to n do if xi = yj then c[i, j]= c[i -1,j -1] + 1 b[i, j] =” “ if else c[i -1, j ] ≥ c[i , j -1 ] then c[i, j]= c[i -1,j ] b[i, j] =” “ else c[i, j]= c[i,j - 1] b[i, j] = ” “ return c y b. La fig. 2 muestra la tabla que se genera por el procedimiento anterior sobre la secuencia X= <A, B, C, B, D, A, B> e Y= < B, D, C, A, B, A>. El tiempo de ejecución del procedimiento es claramente O(mn).



23

El siguiente procedimiento recursivo imprime la salida de LCS de X e Y. La llamada inicial es printLCS(b, X, long[X], long[Y]). printLCS(b, X, i, j). if i=0 o j=0 then return if b[i, j] = “ ” then printLCS(b, X, i -1, j -1) print xi else if b[i, j] = “ ” then printLCS(b, X, i -1, j ) else printLCS(b, X, i , j – 1 ) Para la tabla b en Fig. 2 este procedimiento imprime”BCBA”. Implementación /* Hallar la Longest Common Subsequence, LCS de 2 secuencias como entrada, usando Programación Dinámica. Considerar que el programa lee los argumentos de la línea de comando. El primer argumento es la cadena X de caracteres o string, en este caso se consideran solo enteros(int) mientras que el segundo argumento es la cadena Y de caracteres o string, también enteros(int). la linea de comando es: x1 x2 ... xm . y1 y2 ... yn Para notar el termino de una cadena con respecto al inicio de la otra se considera un punto "." como separador. Ejemplo de uso >java LCS 1 0 0 1 0 1 0 1 . 0 1 0 1 1 0 1 1 0 1 0 0 1 0 1 0 1 0 1 0 1 1 0 1 1 0 LCS tiene longitud: 6 1 0 0 1 1 0 */ public class LCS { public static void main(String[] args) { int[] x, y; // las 2 secuencia int n, m; // x's van de x1 a xn; y's van de y1 a ym int[][] longit; // longit[i][j] es la longitud de la subsucesion //comun mas grande de la long-i subsucesion de los x's, y la long-j //subsucesion de los y's. int[][] reconstruir;//es la variable "b" , //util para simplificar la construccion de una solucion optimal. int i, j, k, xs, ys; // lee la linea de comando con los argumentos k = args.length; i=0; while (! args[i].equals(".")) i++; n = i; m = k - i-1; x = new int[n+1]; // parten los indices en 1 y = new int[m+1];



24

for (j=0; j<i; j++) x[j+1] = Integer.parseInt(args[j]); for (j=0; j<k-i-1; j++) y[j+1] = Integer.parseInt(args[i+1+j]); longit = new int[n+1][m+1]; reconstruir = new int[n+1][m+1]; System.out.println(); for (j=1; j <= n; j++) System.out.print(x[j]+" "); System.out.println(); for (j=1; j<= m; j++) System.out.print(y[j]+" "); System.out.println(); //Si uno del par de sucesiones tiene longitud 0, entonces el //largo de su LCS es también 0. for (xs = 1; xs <= n; xs++) longit[xs][0] = 0; for (ys = 1; ys <= m; ys++) longit[0][ys] = 0; // Ahora calculamos LCS que sucesivamente compara prefijos de x // con prefijos de y for (xs = 1; xs <= n; xs++) { for (ys = 1; ys <= m; ys++) { if (x[xs] == y[ys]) { longit[xs][ys] = longit[xs - 1][ys - 1] + 1; reconstruir[xs][ys] = 3; // "3" es la flecha diagonal. //Indica los elementos que han sido seleccionados // (vea CLR pag. 317) } else if (longit[xs - 1][ys] >= longit[xs][ys-1]) { longit[xs][ys] = longit[xs-1][ys]; reconstruir[xs][ys] = 1; // "1" es la flecha horizontal } else { longit[xs][ys] = longit[xs][ys-1]; reconstruir[xs][ys] = 2; // "2" es la flecha vertical } } } System.out.println("LCS tiene longitud: " + longit[n][m]); printLCS(reconstruir, x, n, m); System.out.println(); } private static void printLCS(int[][] reconstruir, int[] x, int n, int m) { if (n==0 || m==0) { System.out.println(); return; } else if (reconstruir[n][m] == 3) {



25

printLCS(reconstruir, x, n-1, m-1); System.out.print(" " + x[n]); } else if (reconstruir[n][m] == 2) printLCS(reconstruir, x, n, m-1); else printLCS(reconstruir, x, n-1, m); } } Aqui aparece con un MVC asociado.

Bajo un esquema similar es posible presentar la siguiente aplicación: Dada una sucesión de enteros X = < x1 , x2 , ....., xm >, los cuales no contienen elementos duplicados, entonces es posible diseñar un algoritmo para encontrar la subsucesión creciente más grande xi1 < xi2 < .... < xik, donde i1 < i2 < .... < ik que puede encontrarse en X. También conocido como Longest increasing subsequence. (LIS). Por ejemplo, la subsucesión más grande de {3, 1, 4, 5, 9, 2, 6, 0, 7, 8, 12, 10} es {3, 4, 5, 6, 7, 8, 12} y otra es {1, 4, 5, 6, 7, 8, 10}. Implementación: /* Observación: Esta es una solucion para encontrar una ( de varias posibles) subsucesión creciente más larga que esta insertada en una sucesión de simbolos. Ejemplo de uso: $ java LIS 3 5 6 8 9 12 23 4



26

3 5 6 8 9 12 23 4 ^ ^ ^ ^ ^ ^ ^ Una LIS tiene longitud 7. */ public class LIS { public static void main(String[] args) { int n; // la longitud de la suc de entrada int[] x; // la sucesion de entrada int[] lis; // lis[i] es la longitud de la LIS(longest increasing //subsequence), cuyo miembro final es x[i]. int[] previo; /* si x[i] pertenece a una LIS determinada por el algoritmo, previo[i] es el indice de los predecesor x[i]'s en la LIS. El miembro inicial de la LIS tiene previo[i] = n. */ boolean[] en_LIS; // en_LIS[i] es true ssi x[i] esta en la LIS. int i, j, k, lis_valor, lis_max, k_max, i_max, fin_de_longest; // inicializar variables y leer la sucesión de entrada, desde la línea //de comando. n = args.length; x = new int[n]; lis = new int[n]; previo = new int[n]; en_LIS = new boolean[n]; for (i=0; i < n; i++) x[i] = Integer.parseInt(args[i]); // hallar una LIS, sin contar la existencia del total de ellas. lis[0] = 1; previo[0] = n; i_max = 0; fin_de_longest = 0; for (i=1; i<n; i++) { lis_max = 0; k_max = 0; for (k=0; k < i; k++) { lis_valor = (x[k] < x[i] ? 1 : 0) * lis[k]; if (lis_valor > lis_max) { lis_max = lis_valor; k_max = k; } } lis[i] = lis_max + 1; if (lis_max == 0) previo[i] = n; else previo[i] = k_max; if (lis[i] > i_max) { i_max = lis[i]; fin_de_longest = i; } } //marca todos los elementos que estan en la LIS j = fin_de_longest; en_LIS[j] = true; while (previo[j] != n) {



27

j = previo[j]; en_LIS[j] = true; } //print la sucesión de entrada System.out.println(); for (i=0; i<n; i++) System.out.print(x[i] + " "); System.out.println(); //marca los elementos que estan en la LIS for (i=0; i<n; i++) { if (en_LIS[i]) System.out.print("^" + rellenar(x[i]) + " "); else System.out.print(" " + rellenar(x[i]) + " "); } System.out.println(); System.out.println("Una LIS tiene longitud" + lis[fin_de_longest]); } //return el número de digitos en n private static int digitos(int n) { int m = n / 10; if (m == 0) return 1; else return( 1 + digitos(m)); } /*return un string de whitespace, de longitud una menor que el número de dígitos en el argumenmto de entrada.*/ private static String rellenar(int n) { int d = digitos(n) - 1; StringBuffer rellenar = new StringBuffer(); for (int i = 0; i < d; i++) rellenar.append(" "); return (rellenar.toString()); } } Arboles de Búsqueda Binario Optimal El objetivo del ABBO es minimizar el tiempo medio de búsqueda, dadas las frecuencias de acceso de cada uno de los datos. Una estrategia en los arboles binarios de búsqueda seria colocar los elementos que se acceden con mas frecuencia cerca de la raíz del árbol. Además en estos tipos de arboles siempre se debe respetar la condición de ABB (sub- árbol izquierdo < raíz < sub- árbol derecho). Una estrategia para lograr este objetivo es la Programación Dinámica. La técnica que esta detrás del llenado de la matriz obedece al cálculo de los costos de los posibles sub -árboles optimales dentro de un rango especificado por la ecuación: R C(L,R) = min { C( L , i –1 ) + C( i + 1 , R ) + ∑ Pj } L ≤ i ≤ R j = L



28

Ejemplo Dada la siguiente tabla de palabras junto con sus frecuencias de acceso, se muestran algunos de los cálculos correspondientes a los valores que serán almacenados en las matrices de costos C[i,j] y de raíces R[i,j].

i K i P i 1 A 20 2 Bien 10 3 Con 30 4 De 15 5 El 25

C( 1,2 ) = min { ( C(1,0) + C(2,2) + P1+ P2 ), C(1,1) +C(3,2) +P1 +P2 } i =1 i =2 C(1,2 ) = min { 40 , 50 } = > C(1,2) = 40 ; R(1,2) =1 Cij 1 2 3 4 5 Rij 1 2 3 4 5 1 20 40 1 1 1 2 0 10 2 0 2 3 0 0 30 3 0 0 3 4 0 0 0 15 4 0 0 0 4 5 0 0 0 0 25 5 0 0 0 0 5

C( 2,3 ) = min { ( C(2,1) + C(3,3) + P2+ P3 ), C(2,2) +C(4,3) +P2 +P3 } i =2 i =3 C(2,3 ) = min { 70 , 50 } = > C(2,3) = 50 ; R(2,3) =3 Cij 1 2 3 4 5 Rij 1 2 3 4 5 1 20 40 1 1 1 2 0 10 50 2 0 2 3 3 0 0 30 3 0 0 3 4 0 0 0 15 4 0 0 0 4 5 0 0 0 0 25 5 0 0 0 0 5

C( 3,4 ) = min { ( C(3,1) + C(3,3) + P3+ P4 ), C(3,2) +C(4,3) +P3 +P4} i =3 i =4 C(3,4 ) = min { 60 , 75 } = > C(3,4) = 60 ; R(3,4) =3 Cij 1 2 3 4 5 Rij 1 2 3 4 5 1 20 40 1 1 1 2 0 10 50 2 0 2 3 3 0 0 30 60 3 0 0 3 3 4 0 0 0 15 4 0 0 0 4 5 0 0 0 0 25 5 0 0 0 0 5

C(4,5 ) = min { 65 , 55 } = > C(4,5) = 55 ; R(4,5) =5 Cij 1 2 3 4 5 Rij 1 2 3 4 5 1 20 40 1 1 1



29

2 0 10 50 2 0 2 3 3 0 0 30 60 3 0 0 3 3 4 0 0 0 15 55 4 0 0 0 4 5 5 0 0 0 0 25 5 0 0 0 0 5

C(1,3 ) = min { 110 , 110 , 100 } = > C(1,3) = 100 ; R(1,3) = 3 Cij 1 2 3 4 5 Rij 1 2 3 4 5 1 20 40 100 1 1 1 3 2 0 10 50 2 0 2 3 3 0 0 30 60 3 0 0 3 3 4 0 0 0 15 55 4 0 0 0 4 5 5 0 0 0 0 25 5 0 0 0 0 5

C(2,4 ) = min { 115 , 80 , 105 } = > C(2,4) = 80 ; R(2,4) = 3 Cij 1 2 3 4 5 Rij 1 2 3 4 5 1 20 40 100 1 1 1 3 2 0 10 50 80 2 0 2 3 3 3 0 0 30 60 3 0 0 3 3 4 0 0 0 15 55 4 0 0 0 4 5 5 0 0 0 0 25 5 0 0 0 0 5

C(3,5 ) = min { 125 , 125 , 130 } = > C(3,5) = 125 ; R(3,5) = 4 En caso de que dos costos se repitan y sean mínimos, se escoge aquel que esta asociado al subíndice i mayor. Cij 1 2 3 4 5 Rij 1 2 3 4 5 1 20 40 100 1 1 1 3 2 0 10 50 80 2 0 2 3 3 3 0 0 30 60 125 3 0 0 3 3 4 4 0 0 0 15 55 4 0 0 0 4 5 5 0 0 0 0 25 5 0 0 0 0 5

C(1,4 ) = min { 155 , 155 , 130 , 175 } = > C(1,4) = 130 ; R(1,4) = 3 Cij 1 2 3 4 5 Rij 1 2 3 4 5 1 20 40 100 130 1 1 1 3 3 2 0 10 50 80 2 0 2 3 3 3 0 0 30 60 125 3 0 0 3 3 4 4 0 0 0 15 55 4 0 0 0 4 5 5 0 0 0 0 25 5 0 0 0 0 5

C(2,5 ) = min { 205 , 145 , 155 , 160 } = > C(2,5) = 145 ; R(2,5) = 3 Cij 1 2 3 4 5 Rij 1 2 3 4 5 1 20 40 100 130 1 1 1 3 3 2 0 10 50 80 145 2 0 2 3 3 3 3 0 0 30 60 125 3 0 0 3 3 4 4 0 0 0 15 55 4 0 0 0 4 5 5 0 0 0 0 25 5 0 0 0 0 5

C(1,5) = min {245, 245, 195, 225, 230} = > C(1,5) = 195; R(1,5) = 3



30

Cij 1 2 3 4 5 Rij 1 2 3 4 5 1 20 40 100 130 195 1 1 1 3 3 3 2 0 10 50 80 145 2 0 2 3 3 3 3 0 0 30 60 125 3 0 0 3 3 4 4 0 0 0 15 55 4 0 0 0 4 5 5 0 0 0 0 25 5 0 0 0 0 5

La construcción del árbol es un proceso recursivo, el cual consiste en tomar los sub índices del primer arreglo y localizarlos en la matriz de raíces. Se asigna el elemento R[1,n] de esa matriz y pasa a ser la raíz del ABBO subdividiendo el arreglo en una mitad que representa al sub árbol izquierdo y otra al sub árbol derecho, repitiéndose este proceso hasta encontrar una matriz de dimensión 1x1, que representara una hoja en el árbol final. Rij 1 2 3 4 5 1 1 1 3 3 3 2 0 2 3 3 3 3 0 0 3 3 4 4 0 0 0 4 5 5 0 0 0 0 5

A Bien Con De El 1 2 3 4 5 Rij 1 2 3 4 5 1 1 1 3 3 3 2 0 2 3 3 3 3 0 0 3 3 4 4 0 0 0 4 5 5 0 0 0 0 5

Las sub-matrices restantes son de 1x 1 entonces se localizan en el árbol cumpliendo la condición de ABB, quedando así el siguiente ABBO. Rij 1 2 3 4 5 1 1 1 3 3 3 2 0 2 3 3 3 3 0 0 3 3 4 4 0 0 0 4 5 5 0 0 0 0 5

Con

A Bien 1 2

De El 4 5

Con

A El

Bien 2

De 4

Con

A El

Bien De



31

d) Problemas de optimización y algoritmos avaros (greedy) En esta sección estudiaremos varios problemas de optimización que se pueden resolver empleando algoritmo codiciosos o estrategia Greedy. Es común que en los problemas de optimización el algoritmo tenga que tomar una serie de decisiones cuyo efecto general es reducir al mínimo el costo total, o aumentar al máximo el beneficio total, de algún sistema. El método codicioso consiste en tomar sucesivamente, las decisiones de modo que cada decisión individual sea la mejor de acuerdo con algún criterio limitado "a corto plazo" cuya evaluación no sea demasiado costosa. Una vez tomada una decisión, no se podrá revertir, ni siquiera si más adelante se hace obvio que no fue una buena decisión. Por esta razón, los métodos codiciosos no necesariamente hallan la solución óptima exacta de muchos problemas. No obstante, en el caso de los problemas que se estudiaran en este capítulo, es posible demostrar que la estrategia codiciosa apropiada produce soluciones óptimas. También se abordaran problemas con los que estrategias codiciosas muy similares fracasan. En general la estrategia Greedy trabaja en fases. En cada fase, se realiza una decisión que aparentemente es la mejor, sin considerar o lamentar futuras consecuencias. Generalmente, esta idea es pensada como escoger algún óptimo local. Si se resume la estrategia como "toma lo que puedas obtener ahora" podrá entender el porque del nombre de esta clase de algoritmos. Cuando el algoritmo termina tendremos la esperanza que el óptimo local es igual al óptimo global. Si este es el caso, entonces el algoritmo es correcto, de otra manera el algoritmo a generado una solución suboptimal. Si la "mejor" respuesta no es requerida entonces los algoritmos greedy son a menudo usados para generar respuestas aproximadas, en vez de usar algoritmos más complicados que requieren de otra estrategia para generar "la" respuesta correcta. En general la estrategia Greedy trabaja en etapas "Top-Down" realizando una elección greedy después de la otra. En resumen, la estrategia Greedy consiste de dos partes: 1. Subestructura Optimal 2. Partir con elección de óptimos locales y continuar haciendo elecciones localmente optimales, hasta que la solución es encontrada. Ejemplos: Problema Arbol Expandido Minimal ( Minimum Spanning Trees) “Dado un grafo no-dirigido y conexo G = <V,E>, donde cada arco tiene asociado una "longitud" o "peso", se desea un subconjunto T, de arcos E, tal que el grafo restante sea conexo si solamente los arcos en T son usados, y la suma de los pesos de los arcos es el más pequeño posible. Tal subconjunto debe formar un subgrafo que es un árbol, al cual se le llama Minimum Spanning Tree.” Otro problema: En el proceso de cambio de monedas, por ejemplo $15.530 puede expresarse en $15.530 = 1 * $10.000 + 1 * $ 5.000 + 1 * $ 500 + 3 * ($10). En total se requieren 5 elementos. Al hacer esto estamos seguro de que el número de billetes y monedas es el mínimo. Los problemas de tráfico son típicos casos en que las elecciones óptimas locales no siempre funcionan. Si duda, pregunte en Santiago sobre el resultado de las vías exclusivas que luego pasaron a ser vías …..y ahora el transantiago. (Problema de Planificación) Dado los trabajos t 1, t 2, ... t n, con tiempos t’1, t‘2, ... t’n y un solo procesador. Cuál es la mejor forma de planificar esos trabajos a fin de minimizar el tiempo medio de terminación?



32

Compresión de archivos. (Código de Huffman) Un código de longitud fija de un alfabeto A= { a1 , a2 , ..., am } con m-letras es una expresión en donde cada letra ai = ci,1 ci,2 ...ci,n , en donde i= 1, ...m, y donde cada ci,j fes un elemento de algún conjunto de símbolos. El conjunto C= { ci,1 ci,2 ...ci,n , tal que, i= 1, ...m,} es llamado código de longitud fija de longitud n, y cada ci,1 ci,2 ...ci,,n es llamado código. Ejemplo: Sea A= { a, b, c, d }, entonces { a= 00, b= 01, c=10, d=11} es un código de longitud fija para A y { 00, 01, 10, 11} es el código binario de longitud fija de tamaño n, donde los símbolos del conjunto es {0, 1]. Ejemplo: Código ASCII es un código binario de longitud fija de longitud 8. Toda letra o carácter es codificado con string de 8-bit. Por otra parte, un código de longitud variable de un alfabeto A= { a1,a2 , ..., am } con m-letras es una expresión en donde cada letra ai = ci,1 ci,2 ...ci, li , en donde i= 1, ...m, y donde cada ci,j fes un elemento de algún conjunto de símbolos. El conjunto C= { ci,1 ci,2 ...ci,,li , tal que, i= 1, ...m,} es llamado código de longitud variable, y cada ci,1 ci,2 ...ci, li es llamado código. Ejemplo: Sea A= { a, b, c, d }, entonces { a= 0, b= 110, c=10, d=111} es un código de longitud variable para A y { 0, 110, 10, 111} es el código binario de longitud variable, donde los símbolos del conjunto son de {0, 1]. Se dice, que un código es “prefijo” si ningún código es un prefijo de algún otro. Ejemplo: Sea A= { a, b, c, d }, entonces { a= 0, b= 110, c=10, d=111} es un código prefijo, pues al recibir el mensaje 1100111 tiene una única decodificación “bad”. Por otra parte, si { a= 1, b= 110, c=10, d=111}, entonces { 1,110, 10, 111}, no es un código prefijo, pues al recibir el mensaje 110 podría ser decodificado en “b” o “ac”. El problema es, suponga que tenemos un archivo de dato con 100.000-caracteres que se desea compactificar, observamos que los caracteres que ocurren con sus respectivas frecuencias son: 6 caracteres, a, b, c, d, e y f con frecuencias 45, 13, 12, 16, 9 y 5, respectivamente (en miles). ¿Cuál es el código de longitud fija y variable que usa el menor espacio?. Una propuesta es: Caracteres a b c d e f Frecuencia 45 13 12 16 9 5 Código long. Fija 000 001 010 011 100 101 Código long. Var. 0 101 100 111 1101 1100 Para almacenar 100 de estos caracteres, código de long. Fija requiere 100*3 = 300 bits, mientras que código de long. variable requiere 45*1+13*3+12*3+16*3+9*4+5*4=224, ahorrando casi un 25%, de manera que podemos en principio afirmar que códigos de longitud variable son mejores. Dado un alfabeto A con frecuencia de distribución { f(a), a ε A}, el código Huffman construye un árbol binario T, donde los nodos consisten de algunas letras de A y algunas nuevas letras junto con su frecuencia, las hojas consisten de solamente letras de A, todo nodo tiene 2 hijos, hijo izquierdo, rotulado con 0 e hijo derecho rotulado con1. El código para cada letra es la sucesión de bits rotulados sobre el único camino desde la raíz a la hoja.



33

Etapa1: Tomar 2 letras con la frecuencia más pequeña de ocurrencia y crear un subárbol que tiene estos 2 caracteres como hojas. Etapa2: Ahora imaginemos que este subárbol representa un nuevo carácter cuya frecuencia es igual a la suma de las frecuencias de las 2 letras, de manera que se obtiene un nuevo alfabeto con una letra menos. Se repite este proceso, llamada merge, con el nuevo alfabeto hasta que el alfabeto tiene una letra. Ejemplo: Sea A= {f/5, e/9, c/12, b/13, d/16, a/45}, el alfabeto con sus frecuencias de distribución. El código se obtiene como sigue: 0 1 El nuevo alfabeto es A1 = {c/12, b/13, n1/14, d/16, a/45}, 0 1 0 1 El nuevo alfabeto es A2 = {n1/14, d/16, n2/25, a/45}, 0 1 0 1 0 1 El nuevo alfabeto es A 3 = {n2/25, n3/30, a/45}, continuando se obtiene, 0 1 0 1 0 1 0 1

c/12 b/13 n1/14 d/16

f/5 e/9

n1/14 n2/25 a/45

c/12 b/13 f/5 e/9

a/45

d/16

n2/25 n3/30 a/45

n1/14 d/16 c/12 b/13

f/5 e/9

a/45 n4/55

n2/25

c/12 b/13

n3/30

n1/14 d/16

f/5 e/9



34

El nuevo alfabeto es A4 = {n4/55, a/45}, y finalmente se tiene 0 1 0 1 0 1 0 1 0 1 El nuevo alfabeto es A5 = {n5/100}. El código Huffman es obtenido desde el árbol binario rotulado. En efecto, a=0, b=101, c= 100, d=111 , e=1101, f= 1100. Algoritmo: Dado un alfabeto A con distribución de frecuencia { f(a), a ε A}, una prioridad Q, claves sobre f, que es usada para identificar las 2 letras con menor frecuencia. Se tiene, Huffman(A) { n=|A|; Q=A; for i=1 to n-1 { z=localizar() x= Izq[z] = Extraer_Min(Q); y= Der[z] = Extraer_Min(Q); f[z]= f[x] + f[y]; Insertar(Q, z); } return Extraer_Min(Q)//raíz del árbol binario El tiempo de ejecución es O(nlogn), ya que cada operación prioridad toma tiempo O(logn). Este algoritmo es para construir el árbol de Huffman, y luego a partir de él construir el código de Huffman. Se demuestra que el algoritmo Huffman genera un árbol código prefijo optimal. Desde el punto de vista de su implementación el código Huffman usa "priority_queue" , que es una aplicación usual de los Heaps, la cola de prioridad es una estructura de datos con sólo 2 operaciones, Insertar un elemento y eliminar el elemento que tenga la clave más grande (o pequeña). Si los elementos tienen claves iguales, la regla habitual establece que el primer elemento introducido deberá ser el primero en elimninarse. Por ejemplo, en un sistema de computo de tiempo compartido, un extenso número de tareas pude estar esperando para hacer uso de la CPU. En donde algunas de ellas tendrán mayor prioridad que otras, de ahí que el conjunto de las que esperan forme una cola de prioridad. Propiedades: El elemento que posea la clave mayor está en la cima, y puede extraerse en tiempo constante. Sin embargo, tardará tiempo O(log(n)) en restablecer la propiedad de heap

n5/100

n4/55

n2/25

c/12 b/13

n3/30

n1/14 d/16

f/5 e/9

a/45



35

para el resto de las claves. Ahora si otro elemento ha de insertarse de inmediato, parte de ese tiempo puede combinarse con el tiempo O(log(n)) necesario para insertar el nuevo elemento. De esta manera, la representación de una cola de prioridades como heap resulta ventajoso par un n-grande, ya que se representa eficientemente en el almacenamiento contiguo y se garantiza que sólo requerirá tiempo algorítmico para las inserciones y las eliminaciones. Como ya se vió el objetivo es buscar un codigo variable binario apropiado, cuya frecuencia de los datos de entrada sea considerada. El algoritmo de Huffman realiza la codificación binaria con ayuda de los árboles binarios, que se vé de la siguiente manera: Cada nodo tiene un peso, cuyo lugar en el árbol de Codificación de Huffman esta predeterminado, lo que se logra a través de "priority_queue" , en donde según la frecuencia de los símbolos se van disponiendo. Luego, son los nodos de más baja frecuencia eliminados, para ser reemplazados por un nodo interno que contiene la suma de los nodos internos eliminados. El nuevo nodo es vuelto a poner en la priority_queue , este proceso se repite hasta que solamente quede un solo nodo en la la priority_queue como raíz del “nuevo” árbol. Los rótulos de los arcos en el árbol binario desde la izquierda de su nodo padre se rotula con 0, arcos a la derecha con 1. El rótulo de sus hojas es consecuencia de los rotulos de sus arcos sobre el camino desde la raíz a la hoja (como se puede ver 0000, 001, 1001, etc). Implementación /* Observación: Esta es una greedy solucion para minimizar el largo del camino externo ponderado de un arbol. Como ejemplo se muestra la implementación de compresión de huffman. Esta solución usa arboles y priority queue. Ejemplo de uso: $ java Cod_Huffman a 45 b 13 c 12 d 16 e 9 f 5 d=111 e=1101 f=1100 b=101 c=100 a=0 */ public class Cod_Huffman { public static void main (String[] arg) { if (arg.length == 0) { System.out.println ( "Use: java Cod_Huffman simbolo frecuencia [simbolo peso ...]"); return; } //formateando la entrada de datos int tamaño = arg.length / 2; // numero de items PQ queue = new PQ(); int peso; char simbolo; Arbol_Peso hoja; // incorporando el peso en la priority queue for (int item=0; item < tamaño; item++) { peso = Integer.parseInt(arg[item*2 + 1]); simbolo = arg[item*2].charAt(0);



36

hoja = new Arbol_Peso (peso,simbolo); queue.insertar(hoja); } // combina repetidamente los pesos más pequeños de los árboles, // el rotulo "1" esta a la derecha Arbol_Peso chico; Arbol_Peso sig_chico; Arbol_Peso combina; while (! queue.isSingleton()) { chico = queue.getMin(); sig_chico = queue.getMin(); combina = new Arbol_Peso(chico, sig_chico); queue.insertar(combina); } // print los resultados printTabla (queue.getMin(),""); } public static void printTabla (Arbol_Peso arbol, String prefijo) { if (arbol.izq == null) { // una hoja System.out.println(arbol.simbolo()+"="+prefijo); } else { printTabla (arbol.der,prefijo+"1"); printTabla (arbol.izq, prefijo+"0"); } } } //------------------------------------------------------------- // Arboles ponderados para representar código de huffman // inicialización a través del constructor Arbol_Peso() class Arbol_Peso { private int peso; private char caracter; public Arbol_Peso izq; public Arbol_Peso der; public Arbol_Peso (int peso, char caracter) { this.peso = peso; this.caracter = caracter; this.izq = null; this.der = null; } public Arbol_Peso(Arbol_Peso izq, Arbol_Peso der) { this.izq = izq; this.der = der; this.peso = izq.peso + der.peso; } public int valor () { return this.peso; } public char simbolo () { return this.caracter; } }



37

//---------------------------------------------------------------- // Una Priority Queue (PQ)(para Arbol_Peso) // usa un loop en vez de una llamada recursiva para mayor rapidez. class PQ { private PQnodo primer=null; public boolean isSingleton() { return (primer.sig == null); } public Arbol_Peso getMin () { Arbol_Peso minArbol = primer.arbol; primer = primer.sig; return (minArbol); } public void insertar(Arbol_Peso newArbol) { primer = insertNodo(newArbol, primer); } private PQnodo insertNodo (Arbol_Peso newArbol, PQnodo nodo) { if ((nodo==null) || (newArbol.valor()<nodo.arbol.valor())) return (new PQnodo (newArbol, nodo)); else { nodo.sig = insertNodo (newArbol, nodo.sig); return (nodo); } } } class PQnodo { public Arbol_Peso arbol; public PQnodo sig; public PQnodo (Arbol_Peso arbol, PQnodo sig) { this.arbol = arbol; this.sig = sig; } } Aqui aparece con un MVC asociado.



38

Problema de la mochila Dado n-objetos y una mochila de capacidad M, en donde el objeto i tiene un peso wi, Se deja un porcentaje xi, (0 ≤ xi, ≤ 1) del objeto i en la mochila, para obtener una ganancia o profit pi xi. El objetivo es entonces completar la carga de la mochila con la máxima ganancia o profit que pueda soportar, y que no exceda la capacidad M. Formalmente se desea maximizar n n

(1) ∑ p i x i , con la condición (2) ∑ w i x i ≤ M, y i =1 i =1 (0 ≤ x i ≤ 1), p i > 0, w i > 0, e (0 ≤ i ≤ n). De manera que cada conjunto de partes (x1, x2, x3,.... xn) que satisfagan las condiciones (2) y (3) es una posible solución. Una solución optimal es una solución posible, para lo cual la condición (1) es un máximo. Existe otra versión del problema llamada versión 0-1 del problema de la mochila, pues no existen fracciones de las especies, es decir o se toma o se deja. Sin embargo, se puede demostrar que tienen subestructuras optimal, esto es que si eliminamos j- item de las especies optimales, el resto debe seguir siendo optimal para W - w j. Por ejemplo, para el caso en que n=3 (número de objetos), M=20 capacidad de la Mochila, y los valores (p1 , p2 , p3) = (25, 24, 15) y (w1 , w2 , w3) = (18, 15, 10), se obtienen 4-posibles soluciones



39

(x1 , x2 , x3) suma (w i xi ) suma(pi xi ) (i) (1/2, 1/3, ¼) 16.5 24.25 (ii) (1, 2/15, 0) 20 28.2 (iii) (0, 2/3, 1) 20 31 (iv) (0, 1, ½) 20 31.5 es claro que de estas 4-soluciones la (iv) alcanza su máximo profit. Tras este algoritmo se muestra un problema de Optimización, en el sentido de hallar la utilidad total más grande que cualquier subconjunto de los objetos que quepa en la mochila(y hallar un subconjunto que produzca la utilidad máxima). Así como un problema de Decisión, pues dado k, ¿existe un subconjunto de los objetos que quepa en la mochila y tenga una utilidad total de por lo menos k?. El problema de la mochila tiene diversas aplicaciones en planificación económica y en problemas de carga o empaque. Por ejemplo, podría describirse un problema de toma de decisiones de inversión en el que el “tamaño” de una inversión es la cantidad de dinero requerida, M es el capital total que se puede invertir y la “utilidad” de una inversión es el rendimiento esperado. Cabe señalar que el problema de la mochila es de maximización. Implementación: /* Archivo MochilaGreedy.java Esta es una solución greedy para el problema de la mochila fraccionario. Los argumentos en la línea de comando son p1, w1, p2, w2, ..., pn, wn. donde p1 w1 corresponde al valor y peso del objeto1 respectivamente, y así sucesivamente. Ejemplo de uso: >java MochilaGreedy 25 18 24 15 15 10 Profit Peso fit 24 15 1.0 15 10 0.5 25 18 0.0 Total Profit:31.5 */ public class MochilaGreedy { private static int maxPeso = 20; // lo que la mochila puede soportar public static void main (String[] argumentos) { if (argumentos.length == 0) { System.out.println ( "Use: java MochilaGreedy profit peso [valor peso ...]"); return; } int tam = argumentos.length / 2; // numero de objetos Mochila_objetos [] objs = new Mochila_objetos[tam]; float [] fit = new float[tam]; // ingreso para los objetos en la Mochila // ingresa los datos valor y peso en el objeto array int profit; int peso; for (int obj=0; obj < tam; obj++) { profit = Integer.parseInt(argumentos[2*obj]);



40

peso = Integer.parseInt(argumentos[2*obj+1]); objs[obj] = new Mochila_objetos(profit, peso);// creacion de un objeto fit[obj] = 0; // ningun objeto en la mochila inicialmente } //ordena los objetos en orden decreciente por métrica //ordenar (objs); // hace el manejo (GREEDY) float espacioIzq = maxPeso; int obj=0; while ((espacioIzq>0) && (obj<tam)) { peso = objs[obj].getPeso(); if (peso > espacioIzq) { fit[obj] = espacioIzq / peso; espacioIzq = 0; } else { fit[obj] = (float) 1.0; espacioIzq = espacioIzq - peso; } obj++; } displayObjetos(objs, fit); } // --------------------------------------------------------------- // display el listado de los datos del objeto public static void displayObjetos (Mochila_objetos[] objs, float[] fit) { // print los datos en este formato System.out.println ("\nProfit\tPeso\tfit"); float totalProfit=0; int profit; int peso; float suma; for (int pos=0; pos < objs.length; pos++) { profit= objs[pos].getProfit(); peso= objs[pos].getPeso(); suma= fit[pos]; totalProfit = (profit*suma) + totalProfit; System.out.println(" "+profit+"\t "+peso+"\t"+fit[pos]); } System.out.println("\nTotal Profit: "+totalProfit); } //--------------------------------------------------------------- // sort los objetos en orden decreciente basado en la metrica public static void ordenar (Mochila_objetos[] array) { int ult = array.length - 1; Mochila_objetos temp; for (int actual=0; actual < ult; actual++) { for (int obj=actual+1; obj <= ult; obj++) { if (array[actual].getMetric() < array[obj].getMetric()) { temp = array[obj]; array [obj] = array[actual]; array [actual] = temp; } }



41

} } } //------------------------------------------------------------- // objetos para representar los objetos de la mochila. Cada uno tiene //un profit y un peso como metrica - maximizamos esto en cada etapa del //algoritmo Greedy class Mochila_objetos { private int profit; private int peso; private float metrica; // la metrica greedy public Mochila_objetos(int profit, int peso) { this.profit = profit; this.peso = peso; this.metrica = (float) profit / (float) peso; } public int getProfit () {return this.profit;} public int getPeso () {return this.peso;} public float getMetric () {return this.metrica;} } Existe otra versión considerando que el objeto o se toma o se deja, de ahí el considerar 0 o 1, conocido como “Knapsack 0-1”. Una descripción formal es: Dados los vectores de valores < v1, v2, v3 .. vn >, y pesos < w1, w2, w3 .. wn >, correspondiente a n-objetos, tal que M > 0. Se pide determinar el conjunto T⊆ {1, 2, 3, 4,...n}, (de objetos a tomar) que logra maximizar n

(1) ∑ vi , sujeta a la condición (2) ∑ w i ≤ M. i ∈ T i ∈ T La idea que se trabaja en este contexto es la de Programación dinámica, recordemos que la programación dinámica es un approach para resolver problemas de optimización, y es por eso que ve en este contexto. En este contexto se computan las soluciones a los subproblemas una vez y se almacenan en una tabla de manera que ellos puedan ser reutilizados más tarde. Etapa1: Caracterizar la estructura de una solución optimal(Estructura), es decir descomponer el problema en subproblemas más pequeños y encontrando en ellos una relación entre las estructuras de la solución optimal al problema original con los problemas más pequeños. Etapa2: Recursivamente se definen los valores de una solución optimal (Principio de Optimabilidad), es decir expresar la solución del problema original en términos de soluciones optimales de los problemas más pequeños. Etapa3: Computar el valor de una solución optimal en la forma bottom-up usando la estructura de la tabla. (Computación Bottom-up ) Etapa4: Construcción de una solución optimal desde la información computada. (Construcción de la solución optimal). Etapas3 y 4 pueden ser combinadas, sin embargo las etapas 1-3 forman la base a la solución de problemas vía programación dinámica. Etapa4 puede ser omitida si solamente los valores



42

de una solución optimal son requeridos. En general, la programación en programación dinámica se refiere al “método de la tabla”. Ejemplo para el caso 0-1, consideremos la fig. XX en donde la fila i representa los objetos, la fila vi los valores y wi los pesos. La matriz V[i, w] es la matriz o tabla en donde se registran

los cálculos, al ver la tabla Ud. notará que la solución se obtiene en la posición V[4, 10]= 90 que es la solución optima, cuyos subconjuntos son T ={2, 4}={(4, 40), (3, 50)}. Observación: Basado en el ejemplo anterior y la propuesta siguiente Objetos Valor Peso Valor/Peso 1 60 10 6 2 100 20 5 3 120 30 4 podrá constatar que siendo la capacidad igual a M=50, la solución greedy seleccionaría 1, cuyo capacidad máxima es 60, con un resto de 40 Kg. A este punto, si escogemos los objetos 1 y 2 el valor total es 160, y si escogemos los objetos 1 y 3 el valor total es 180. Sin embargo, la solución optimal se logra al escoger los objetos 2 y 3. De donde el valor total de esta solución es 220. Implementación /* En general se tiene una mochila que puede soportar un peso total M, así como un juego de N objetos, en que cada uno tiene un wi de peso y un pi de valor. Los objetos son únicos, en el sentido de incluirlos en la mochila o dejarlos, es decir no tiene sentido en este contexto tomar una porción, porcentaje, parte o múltiplos de la inclusión de un objeto. Se desea empacar en nuestra mochila los objetos de mayor valor, cuya capacidad total <= W. Considerar que el programa lee los argumentos de la línea de comando. El primer argumento es la capacidad maxima admisible, y los siguientes valores son pares asociados a (peso, valor) para cada objeto.



43

Ejemplo de uso >java Mochila01 10 5 10 4 40 6 30 3 50 Capacidad Maxima: 10 (5, 10)(4, 40)(6, 30)(3, 50) Subconj -Valores (4, 40) 40 (3, 50) 50 */ public class Mochila01 { public static void main(String[] args) { int max_capacidad, num_objetos, objs, capacidad, i, longitud, w, cap; int valor0, valor1, max_valor, j; int[] peso, valor; int[][] subsoluciones; int[][][] carga; // Lee los argumentos de la línea de comando. El primer //argumento es capacidad maxima los siguientes son pares asociados a //(peso, valor) para cada objeto. longitud = args.length; max_capacidad = Integer.parseInt(args[0]); num_objetos = (longitud - 1) / 2; peso = new int[num_objetos]; valor = new int[num_objetos]; subsoluciones = new int[num_objetos][max_capacidad+1]; carga = new int[num_objetos][max_capacidad+1][num_objetos]; for (i=0; i<num_objetos; i++) { peso[i] = Integer.parseInt(args[1+2*i]); valor[i] = Integer.parseInt(args[2+2*i]); } System.out.println("Capacidad Maxima: " + max_capacidad); for (i=0; i < num_objetos; i++) System.out.print("("+peso[i]+", "+valor[i]+") "); System.out.println(); // Completamos la primera fila de la matriz de subsoluciones. for (w = 0; w <= max_capacidad; w++) if (peso[0] <= w) { subsoluciones[0][w] = valor[0]; carga[0][w][0] = 1; } else subsoluciones[0][w] = 0; // y se construye la primera columna for (i=0; i<num_objetos; i++) subsoluciones[i][0] = 0; // Ahora completamos las filas restantes de la matriz. En cada //nueva fila consideramos de izquierda a derecha, los datos calculados. for (objs = 1; objs < num_objetos; objs++) { for (cap = 1; cap <= max_capacidad; cap++) { for (j=0; j<objs; j++)



44

carga[objs][cap][j] = carga[objs-1][cap][j]; if (peso[objs] > cap) subsoluciones[objs][cap] = subsoluciones[objs-1][cap]; else { valor0 = subsoluciones[objs-1][cap]; valor1 = subsoluciones[objs-1][cap - peso[objs]] + valor[objs]; if (valor0 > valor1) { subsoluciones[objs][cap] = valor0; } else { subsoluciones[objs][cap] = valor1; for (j=0; j<objs; j++) carga[objs][cap][j] = carga[objs-1][cap-peso[objs]][j]; carga[objs][cap][objs] = 1; } } } } System.out.println(); max_valor = subsoluciones[num_objetos - 1][max_capacidad]; System.out.println("Subconj\t-Valores"); for (j=0; j<num_objetos; j++) { if (carga[num_objetos-1][max_capacidad][j] == 1) System.out.println("("+peso[j]+","+valor[j]+")" + "\t" + valor[j]); } } } e) BACKTRACKING Backtracking (o búsqueda hacia atrás) es una técnica de programación para hacer búsqueda sistemática a través de todas las configuraciones posibles dentro de un espacio de búsqueda. Para lograr esto, los algoritmos de tipo backtracking construyen posibles soluciones candidatas de manera sistemática. En general, dada una solución candidata S, se procede a 1. Verifican si S es solución. Si lo es, hacen algo con ella (depende del problema). 2. Construyen todas las posibles extensiones de S, e invocan recursivamente al algoritmo con todas ellas. A veces los algoritmos de tipo backtracking se usan para encontrar una solución, pero otras veces interesa que las revisen todas (por ejemplo, para encontrar la más corta).



45

EJEMPLO 1: Un problema clásico es el problema del vendedor viajero: Dadas n ciudades conectadas todas con todas, “encontrar el camino que recorra todas las ciudades con mínimo costo”. Se parte de una ciudad cualquiera, y se obtiene el siguiente espacio de soluciones: (1) (1,2) (1,3) ....... (1,n) (1,2,3) (1,2,n) .......... (1,n,2) ...... .................. (1,2,3,4,...,n) En este nivel se tienen todos los posibles caminos junto con su costo asociado. Criterios de poda: cuando se encuentra el primer camino se guarda el camino y su costo como posible solución. Si se encuentra uno mejor se redefine la solución. Si por una rama se detecta que el costo parcial es mayor al costo de la solución alcanzada hasta el momento, entonces podo ese subárbol (pero no a sus hermanos). EJEMPLO 2: Dada una secuencia de n enteros, se desea saber si existe una partición en dos subconjuntos S1 y S2 disjuntos, tal que la suma de sus elementos sea la misma, es decir: Dado S= {s1,s2,...,sn}

Se desea encontrar dos subconjuntos S1 y S2 tal que: S1∩S2 =∅ y Σ sj = Σ si

jεS1 iεS2 Esta partición podría existir como no. Analicemos todo el espacio de soluciones para un ejemplo concreto: S={2, 3, 4, 5, 9, 6, 7 } S1= {2, 3, 4, 9} S2= {5, 6, 7}

S S1= {2} {3} ... {7} S2= {3,4,5,9,6,7} {2,4,5,9,6,7} {2,3,4,5,9,6} {2,3} {2,4} ... {2,7} ... {7,2} ... {7,6} {4,5,9,6,7} {3,5,9,6,7} {3,4,5,9,6} {3,4,5,9,6} {2,3,4,5,9} ... ... ... ... ... {2,3,4} {5,9,6,7}



46

1° nivel 1 2° nivel n .... .... n(n-1) ... n! O(nn) Sobre esto pueden hacerse mejoras: - Evitar generar los mismos subconjuntos: Se puede observar en el árbol que algunas

particiones están repetidas, por ejemplo {2,7}{3,4,5,9,6} y {7,2}{3,4,5,9,6}. Para evitar esto se podrían ordenar los elementos de menor a mayor antes de empezar la búsqueda, y luego si se tiene {7,2}y vemos que 7 >2, esta partición ya fue hecha y seguir en esta rama sería en vano, por lo que se abandona la búsqueda en esa rama, y de esta manera se va podando el árbol.

EJEMPLO 3: Otro tipo de aplicaciones de Backtracking son los juegos. Considere juegos tales como el ajedrez, damas, donde hay dos jugadores. Los jugadores alternan sus movimientos, y el estado del juego puede ser representado por la posición del tablero. Se asume que hay un número finito de posiciones en el tablero y que el juego tiene alguna regla que asegure su terminación. Con cada juego asociamos un árbol llamado árbol del juego. Cada nodo en el árbol representa una posición en el tablero. A la raíz le asociamos la posición de comienzo. Si la posición x está asociada con el nodo n, luego los hijos de n corresponden al conjunto de movidas permitidas desde la posición x, y con cada hijo es asociada la posición del tablero resultante. Por ejemplo la siguiente figura muestra parte del árbol del tic tac toe: juega A ... . . . . . .

juega A juega B juega A

A A A B

B B

A A A A B B B

A A A A B B B

A A A B

B A B

A B A A A B B B

A A A A B B B B

A B A A A B B A B

A B A A B B A B

A A B A B B A B

A B A A A BB A B

A A A B A B B A B

0 0

0 0 1

-1 0

-1

1

1

1

0



47

Las hojas de un árbol de juego corresponden a las posiciones del tablero donde no hay más movimientos, porque uno de los jugadores ha ganado o todos los casilleros están llenos y a ocurrido un empate. Se asocia un valor a cada nodo del árbol. Primero se asignan valores a las hojas planteado desde el punto de vista de uno de los jugadores, tomemos A. Los valores serán -1, 0 o 1, si A pierde, gana o empata respectivamente. Los valores se propagan hacia arriba en el árbol de acuerdo a la siguiente regla: • Si un nodo corresponde a la posición del tablero donde le toca jugar a A, luego el valor con

el que se rotura este nodo es el máximo de los valores de los hijos de este nodo. Es decir, se asume que A hará el movimiento más favorable para sí, el cual produce el valor más alto.

• Si el nodo corresponde a un movimiento de B, el valor con el que rotulamos es el mínimo

de los valores de sus hijos. Es decir, se asume que B moverá inteligentemente, tratando de ganarle a A o por lo menos empatar.

Al terminar el backtracking, se distinguen tres situaciones: 1. Si la raíz tiene un valor 1, el jugador A tiene una estrategia ganadora. Cuando comienza

tiene la garantía de que puede seleccionar un movimiento que lo lleva a la posición del tablero de valor 1. Cuando es el turno del jugador B, éste no tiene mas elección que un movimiento que lo conduce a la posición del tablero de valor 1, una pérdida para él. El hecho de que un juego termine, garantiza una eventual ganancia para el primer jugador.

2. Si la raíz tiene valor cero, como en el caso del ta-te-ti, luego ninguno de los jugadores tiene una estrategia ganadora, solo puede garantizarse a si mismo, empatar jugando tan bien como sea posible.

3. Si la raíz es -1, el jugador B tiene una estrategia ganadora. El siguiente algoritmo determina si existe una estrategia ganadora para A, teniendo en cuenta que: • B juega inteligentemente. • El estado es el tablero, hay que distinguir si el nivel es máx o mín, según juegue A o B

respectivamente. • Hay tres situaciones: A gana (1), A pierde (-1), A empata (0). • Un nodo es una hoja si se da una de las situaciones mencionadas anteriormente. • Poda: si el estado corresponde al nivel de máximo y en un hijo retorna un 1, ya no puede

superarse, se tiene una estrategia ganadora, no se necesita buscar más (no se necesita recorrer sus hermanos), entonces: se poda. En el ejemplo del árbol del ta-te-ti, el primer hijo retorna un 1, por lo tanto no hay necesidad de generar sus hermanos. De la misma forma, si el estado corresponde al nivel de mínimo, si se obtiene un -1, encuentre lo que encuentre más adelante el mínimo será -1, entonces se podan los hermanos.

Geometría Computacional La geometría computacional se encarga del diseño y análisis de algoritmos para resolver problemas geométricos. Los algoritmos geométricos eficientes son muy utilizados en campos como la computación gráfica, la estadística, el procesamiento de imágenes y en el diseño con integración a muy grande escala, también llamado (very-large-scale-integration, VLSI). Algoritmo para calcular la cubierta convexa. Uno de los problemas fundamentales en la geometría computacional es el de calcular los puntos que "acotan" a un conjunto finito de puntos en el plano, formalmente llamado, cubierta convexa.



48

p3 p10 p4 p8 p2 p9 p11 p5 p7 p6 p1

Figura 1 La cubierta convexa tiene aplicaciones en muchas áreas, incluyendo la estadística, pues se puede considerar una muestra de datos que determinen la cubierta convexa, sin embargo es posible dejar estos datos aislados producto de que serán irrelevantes en los cálculos finales. Un algoritmo que presenta una solución a este problema es el realizado por Graham. Definición Dado un conjunto finito de puntos S del plano, un punto p en S es un punto de la cubierta si existe una línea (recta) L que pasa por p de modo que todos los puntos de S, excepto p, están en un lado de L ( y excepto p, ninguno está en L). Ejemplo: p3 p10 p4 p8 p2 p9 p11 p5 p7 L1 p6 p1 L2



49

P1 es un punto de la cubierta, pues podemos determinar una línea L1 que pasa por P, tal que todos los otros puntos están estrictamente a un lado de L1. P8 no es un punto de la cubierta, la línea recta que pasa por P8 corta el plano dejando a ambos lados elementos. Definición La cubierta convexa de un conjunto finito de puntos S del plano es la sucesión p1,p2,....,pn de puntos de la cubierta de S enumerados en el siguiente orden. El punto p1 es el punto con coordenada y mínima. Si existen varios puntos con la misma coordenada y mínima, p1 es el que tiene abscisa mínima(observar que p1 es un punto de la cubierta). Para i>=2 sea αi el ángulo que forma la horizontal con el segmento de recta p1, pi (ver fig. 3). Los puntos p2, p3,...pn se ordenan de modo que α2, α3,..., αn, sea una sucesión creciente. pi αi p1

Figura 3

αi es el ángulo que forma la horizontal con el segmento de recta p1, p2. p3 p10 p4 p8 p2 p9 p11 p5 p7 p6

α2 α3 α4 α5 p1 Mínima

Figura 4



50

P1 tiene la coordenada mínima, de modo que es el primer punto enumerado en la cubierta convexa. Se ve que los ángulos que forman la horizontal con los segmentos de recta P1 ,P2; P1 ,P3; P1 ,P4; P1 ,P5 van creciendo. Así, la cubierta convexa del conjunto de puntos de la Figura 4 es P1 ,P2 , P3, P4, P5. Informalmente para calcular la cubierta convexa de un conjunto finito de puntos S del plano. Primero se determina el punto P1 con coordenada y mínima. Si existen varios puntos con la misma coordenada y mínima, se elige el punto con abscisa mínima. A continuación se “ordenan” todos los puntos P y S de acuerdo con el ángulo que forma la horizontal con el segmento de recta P1,P. Por ultimo se examinan los puntos en orden, y se descartan aquellos que no están en la cubierta convexa. Apresto: Debemos descubrir una forma para comparar ángulos, y debemos desarrollar un métodos para verificar si los puntos están en la cubierta convexa. El resultado será la cubierta convexa. Comparación de Angulos: Supongamos que visitamos los puntos distintos P1 ,P0, P2 en el plano en ese orden. Si después de salir de P0 nos movemos hacia la izquierda decimos que los puntos P1 ,P0, P2 forman un giro a la izquierda. P2 Giro derecha Menor de 180º Giro izquierda mayor de 180º P1 Graham (a) (b) p6 p4 p7 p9 p5 p8 p3 p10 p1 p2

p6 p4 p7 p9 p5 p8 p3 p10 p1 p2



51

(a) El punto p1 tiene la coordenada Y mínima, y entre todos los puntos de este tipo, tiene una

abscisa mínima. Los puntos ordenados según el ángulo de la horizontal con p1, p2, p3 forman un giro hacia la izquierda, de modo que se conserva a p2.

(b) Se examinan p2, p3, p4 · p2, p3, p4 forman un giro a la izquierda, de modo que se conserva

a p2. (c) (d) P6 P4 P7 P9 P5 P8 P3 P10 P1 P2

p6 p4 p7 p9 p5 p8 p3 p10 p1 p2

(c) Se examinan p3, p4, p5 · p3, p4, p5 forman un giro hacia la izquierda de manera que se

conserva a p4. (d) Se examinan p4, p5, p6 · p4, p5, p6 forman un giro hacia la derecha de manera que se

descarta a p5. El algoritmo regresa a p3, p4, p6 , de donde p3, p4, p6 forma un giro a la izquierda, de modo que se conserva a p4. (e) (f) p6 p7 p4 p9 p5 p8 p10 p3 p1 p2

p6 p4 p9 p7 p5 p8 p3 p10 p1 p2



52

(e) Se examina p4, p6, p7 · p4, p6, p7 forman un giro a la izquierda, se conserva p6. (f) Se examina p4, p5, p6 · p4, p5, p6. (g) (h) p6 p7 p4 p9 p5 p8 p10 p3 p1 p2

p6 p4 p7 p9 p5 p8 p3 p10 p1 p2

Finalmente en (i) p6 (i) p4 p7 P9 p5 p8 p3 p10 p1 p2

(g) (i) El algoritmo concluye examinando a p6, p9, p10 · p6, p9, p10 forman un giro a la

izquierda, se conserva p9. De donde la cubierta convexa 1.

p1, p2, p3 , p4, p6, p9, p10



53

ALGORITMO DE GRAHAM Este algoritmo calcula la cubierta de los puntos p1,…,pn del plano. Las coordenadas x y y del punto p se denotan px y py, respectivamente. Entrada: p1,…,pn y n Salida: p1,…,pk (la cubierta convexa de p1,…pn) y k Procedure graham_scan (p, n, k) //caso trivial if n = 11 then begin k := 1 return end // determinar el punto con coordenada y mínima min :=1 for i : = 2 to n do if pi· y < pmin· y then min : = 1 // Entre todos estos puntos, determinar aquél con abscisa mínima // coordenada x for i : = 2 to n do if pi· y = pmin· y and pi· x < pmin· x then min : = i swap (p1, pmin) //ordenar según el ángulo de la horizontal a p1, pi sort p2,…, pn //p0 es un punto adicional, agregado con el fin de evitar que // el algoritmo se repita indefinidamente p0:=pn // descartar los puntos que no están en la cubierta convexa k : = 2 for i : = 3 to n do begin while pk – 1, pk, pi no giran a la izquierda do // descartar pk k := k-1 k:=k+1 swap (pp pk) end end graham_scan EJERCICIO: Utilice Graham para determinar la cubierta convexa de los puntos: (10,1), (7,7), (3,13), (6,10), (16,4), (10,5), (7,13), (13,8), (4,4), (2,2), (1,8), (10,13), (7,1), (4,8), (12,3), (16,10), (14,5), (10,9). Acotación de problemas Hemos visto que en ocasiones para resolver un problema es posible transformarlo en otro equivalente y así resolviendo éste, queda resuelto el problema inicial. Esta técnica es útil en problemas para los cuales se buscan soluciones algorítmicas. Metodología: Suponga que tenemos planteados dos problemas A y B y que para el segundo de ellos se dispone de un algoritmo que lo resuelve. Si somos capaces de transformar los datos de entrada del problema A en una entrada para el algoritmo que resuelve el problema B y la respuesta de



54

éste algoritmo sabemos transformarla en respuesta para el caso particular del problema A de partida, resulta entonces que hemos encontrado un algoritmo para resolver el problema A. Bibliografía: - Introduction to Algorithms, Cormen, Leiserson and Rivest. - Fundamentals of Computers Algorithms, Horowitz - Sahni. - Estructuras de Datos y Algoritmos, Aho - Hopcroft - Ullman. - Algorithms in C, Sedgewick.

Diseño y Análisis de Algoritmos con Java Dr.Eric...

Documents

Transcript of Diseño y Análisis de Algoritmos con Java Dr.Eric...