'Anexo Tema 5.pdf'

ADA Tema 4. Técnicas de Solución de Problemas 1. Introducción 2. Divide y Vencerás 3. Complejidad de los algoritmos de Divide y Vencerás y tiempo de ejecución 4. Problemas que se resuelven con Divide y Vencerás 1. Introducción En este tema vamos a abordar la solución de problemas con diferentes técnicas que estudiaremos. Antes de ver la forma de resolver un problema debemos indicar las características del mismo y modelarlo como un tipo del que podemos crear objetos. Como todos los tipos un problema tendrá diferentes propiedades. Un problema en general lo modelaremos, como hemos visto en el capítulo anterior, mediante el interface genérico Problema<S> donde S es el tipo de la solución del problema. Al tipo que instancie a S le exigiremos en algunos contextos concretos propiedades específicas como que tenga un orden natural o que sea copiable, etc. El interface que representará a un problema en general será: public interface Problema<S> { public static enum TipoDeProblema { UNA_SOLUCION,TODAS_LAS_SOLUCIONES,MEJOR_SOLUCION; } Problema.TipoDeProblema getTipoDeProblema(); } Un problema, con soluciones de tipo S, se resuelve mediante un algoritmo dado. Los tipos de algoritmos que estudiaremos están descritos por el tipo enumerado TipoDeAlgoritmo. Los algoritmos que estudiaremos serán implementaciones del tipo Algoritmo<S>. public interface Algoritmo<S>{ public enum TipoDeAlgoritmo { DIVIDE_Y_VENCERAS_CON_MEMORIA, DIVIDE_Y_VENCERAS_SIN_MEMORIA, PROGRAMACION_DINAMICA, ITERATIVO, VORAZ, RAMIFICA_Y_PODA; } void ejecuta(); Problema<S> getProblema(); Metricas getMetricas(); TipoDeAlgoritmo getTipoDeAlgoritmo(); }

Como vemos un algoritmo tiene las propiedades: • Problema: Problema<S>, es el problema que estamos resolviendo. • Metricas: Metricas, es un objeto que guarda información sobre diferentes propiedades del algoritmo. • TipoDeAlgoritmo: TipoDeAlgoritmo, es el tipo concreto de algoritmo que estamos usando. El método ejecuta pone en funcionamiento el algoritmo. La clase Metricas mide propiedades de un algoritmo en las que podemos estar estamos interesados como por ejemplo TiempoDeEjecucion. Las propiedades que pueden medirse las iremos viendo a medida que sean necesarias. El tipo algoritmo lo especializamos en tres tipos: AlgoritmoConUnaSolucion, AlgoritmoConVariasSoluciones y AlgoritmoConVariosProblemas. Estas especializaciones están pensadas respectivamente, como indica su nombre, para algoritmos que devuelven una solución, varias soluciones o resuelven varios problemas cada uno con una solución. Los interfaces de cada uno de ellos son: public interface AlgoritmoConUnaSolucion<S> extends Algoritmo<S> { S getSolucion(); boolean isSolucion(); } public interface AlgoritmoConVariasSoluciones<S extends Copiable<S>> extends Algoritmo<S> { SortedSet<S> getSoluciones(); Integer getNumeroDeSoluciones(); boolean isSolucion(); S getMejorSolucion(); Set<S> getMejoresSoluciones(); Comparator<S> getOrdenDeSoluciones(); } public interface AlgoritmoConVariosProblemas<S extends Copiable<S>> extends Algoritmo<S> { S getSolucion(Problema<S> p); boolean isSolucion(Problema<S> p); boolean isProblema(Problema<S> p); Integer getNumeroDeProblemas(); Integer getNumeroDeProblemasConSolucion(); } En el algoritmo con varias soluciones asumimos que las soluciones están ordenadas con respecto a un orden y que podemos preguntar por la mejor solución, con respecto a ese orden por todas las soluciones o por las mejores soluciones. En el algoritmo con varios problemas asumimos que se resuelven un conjunto de problemas que comparten datos de algún tipo. En este tipo de algoritmo podemos preguntar si hay solución un problema dado, dentro del rango de problemas considerado, si tiene solución, cual es la solución, el número de problemas considerados o el número de ellos con solución.

2. Divide y Vencerás Para el uso adecuado de esta técnica es conveniente recordar los conceptos de generalización de parámetros y conjunto de problemas. Cuando al problema de partida se le añaden nuevas propiedades para obtener otro problema más general decimos que hemos hecho una generalización de parámetros. En muchos casos es necesario generalizar el problema para resolverlo con mayor facilidad. Como vimos en el capítulo anterior llamaremos conjunto de problemas al conjunto de problemas concretos que pueden obtenerse instanciando, de todas las formas posibles, algunas propiedades escogidas de un problema general dado. En algunas técnicas es muy importante especificar detalladamente el conjunto de problemas con el que estamos trabajando. Dentro de un conjunto de problemas dado podemos distinguir, como para cualquier tipo, dos clases de propiedades: propiedades compartidas por todos los problemas del conjunto y propiedades específicas de cada problema en particular. Como vimos en el capítulo anterior dado un conjunto de problemas podemos escoger dos formas para identificar a cada uno de los problemas concretos. Cada forma tiene sus ventajas e inconvenientes. Estas formas son: • Asociar un objeto a cada problema. Es la técnica más general y sistemática. En el contexto de un conjunto de problemas es suficiente definir la igualdad (y los métodos asociados hashCode, toString, compareTo) en base a las propiedades específicas ignorando las propiedades compartidas. Las propiedades compartidas se pueden implementar de varias maneras: como variables de tipo static compartidas por todos los objetos (problemas) de la clase o como una propiedad más. • Asociar a cada problema un conjunto de parámetros. El conjunto de parámetros representa las propiedades específicas de cada problema. Este modo de representar los problemas concretos es menos reutilizable, como veremos, pero más sencillo de usar en casos simples. La igualdad de dos problemas se implementa como igualdad del conjunto de parámetros que los representan. Las propiedades compartidas pueden implementarse como variables con un ámbito suficientemente amplio o como una propiedad más representada por un parámetro adicional. La primera técnica de solución de problemas que estudiaremos se denomina Divide y Vencerás. El término Divide y Vencerás (en inglés, Divide and Conquer) hace referencia a uno de los más importantes paradigmas de diseño de algoritmos para resolver problemas como los que hemos modelado en el capítulo anterior. El método está basado en la resolución recursiva de un problema dividiéndolo en dos o más sub-problemas de igual tipo o similar. El proceso continúa hasta que éstos llegan a ser lo suficientemente sencillos como para que se resuelvan directamente. Al final, las soluciones a cada uno de los sub-problemas se combinan para dar una solución al problema original.

En esta técnica, y en otras que veremos más adelante, es muy importante detallar el conjunto de problemas con el que estamos tratando. A cada problema del conjunto debemos asignarle un tamaño que medirá el grado de complejidad del problema. En el caso del problema de la Potencia Entera, visto en el capítulo anterior, el tamaño es la propiedad Exponente. Los problemas del conjunto de problemas tenemos que clasificarlos en dos clases: casos base que problemas sencillos que tienen un tamaño pequeño y cuya solución puede ser obtenida directamente y casos recursivos que los problemas que no son casos base. Tras modelar un problema tal como hemos explicado en el capítulo anterior y con las ideas anteriores en mente la resolución del mismo mediante esta técnica consta fundamentalmente de los siguientes pasos: • En primer lugar considerar el conjunto de problemas con el que vamos a tratar. Este conjunto de problemas puede ser obtenido del problema original o de una generalización de parámetros del mismo. Decidir cuál es el tamaño de cada problema y cuáles son las propiedades compartidas y específicas. Clasificar el conjunto de problemas en casos base y casos recursivos. Decidir como representar cada problema del conjunto: mediante un conjunto de parámetros o mediante un objeto. • En segundo lugar han de proporcionarse las soluciones para los problemas que son casos base (es decir los problemas sencillos de tamaño pequeño). • En tercer lugar ha de plantearse la forma de descomponer cada problema del conjunto (que sea un caso recursivo) en varios problemas del mismo conjunto, pero de menor tamaño. A esta tarea se le conoce como división u obtención de los sub-problemas. Si el número de sub-problemas es uno entonces la técnica es conocida como Reducción en vez de Divide y Vencerás. • Por último, combinar las soluciones obtenidas en el paso anterior para construir la solución del problema original. El algoritmo diseñado con la filosofía de Divide y Vencerás funciona de la siguiente manera: si el problema original es un caso base resolver el problema directamente, si es un caso recursivo dividirlo en sub-problemas, resolver recursivamente cada uno de ellos y combinar las soluciones obtenidas. Es muy importante que en el proceso de división el tamaño de cada sub- problema sea menor que el tamaño del problema original. El hecho de que el tamaño de los sub-problemas sea estrictamente menor que el tamaño original del problema nos garantiza la convergencia hacia los casos base y por lo tanto nos garantiza que el proceso termina. Un problema, que se resuelve por la técnica de Divide Y Vencerás, adopta la forma: ݂ሺܺሻ ൌ ൜ܿሺܺ, ݂ሺܺଵሻ, ݂ሺܺଶሻ, … , ܵ଴, ‫݅ݏ‬ ݁‫ݏ‬ ‫݊ݑ‬ ܿܽ‫݋ݏ‬ ܾܽ‫݁ݏ‬ ݂ ሺܺ௞ ሻሻ ‫݅ݏ‬ ݁‫ݏ‬ ‫݊ݑ‬ ܿܽ‫݋ݏ‬ ‫݋ݒ݅ݏݎݑܿ݁ݎ‬ Donde X representa el problema de tamaño n, ܺ௜ los sub-problemas de tamaño ݊௜ con ݊௜ ൏ ݊, c la función que combina las soluciones de los problemas (en el contexto del problema a resolver) y ܵ଴ la solución del caso base de los que puede haber más de uno. Siempre asumiremos un valor de ݂ሺܺሻ que indique que no hay solución. Representaremos este valor



















r = base; return r; } private B dYV(Integer n){ B s; if( esCasoBase(n)){ s = getSolucionCasoBase(n); } else { s = dYV(n/2); s = s.getSquare(); if(Utiles.esImpar(n)) s = s.getMultiplyBase(); } return s; } ... } Como vimos en el capítulo anterior las matrices de Fibonacci son de la forma ቀܽ ൅ ܾ ܾܽቁ. Es ܽ decir dependen de dos parámetros. Para implementar el tipo MatrizFibonacci, cuyos valores son las matrices de Fibonacci, y que extiende BasePotenciaEntera<MatrizFibonacci> hay que tener en cuenta que: ൬݂௡݂௡ାଵ൰ ൌ ቀ11 10ቁ ൬݂௡݂௡ିଵ൰, ܿ‫ ݊݋‬൬݂݂ଵ଴൰ ൌ ቀ01ቁ ‫݋ݐ݊ܽݐ ݋݈ ݎ݋݌‬ ൬݂௡݂௡ାଵ൰ ൌ ‫ܣ‬௡ ቀ01ቁ , ‫ ܣ‬ൌ ቀ11 10ቁ, ݂௡ ൌ ‫ܣ‬௡. ݃݁‫ݐ‬ሺ0,0ሻ Para implementar el tipo MatrizFibonacci (que debe extender el tipo BasePotenciaEntera<MatrizFibonacci>) hay que tener en cuenta las igualdades: ቀܽ ൅ ܾ ܾܽቁଶ ൌ ൬2ܽଶܽ൅ଶ 2ܾܽ ൅ ܾଶ ܽܽଶଶ൅൅2ܾܽଶܾ൰ ; ቀܽ ൅ ܾ ܾܽቁ ‫ כ‬ቀ11 10ቁ ൌ ቀ2ܽܽ൅൅ܾܾ ܽ ൅ ܾቁ ܽ ൅ 2ܾܽ ܽ ܾ La primera nos permite implementar el método getSquare, la segunda getMultiplyBase. Con estas ideas podemos resolver, de nuevo, el problema de Fibonacci con otra técnica: instanciando el Problema Potencia Entera con el tipo MatrizFibonacci implementado. La ficha del problema es ahora: Ficha 4 Problema de Fibonacci Técnica: Instanciación ProblemaPotenciaEntera<MatrizFibonacci> Tamaño: N Propiedades Individuales N, Integer no negativo ݂ሺ݊ሻ ൌ ቀ11 01ቁ௡ . ݃݁‫ݐ‬ሺ0,0ሻ

El test para este problema es: public class TestFibonacci4 extends Test { public static void main(String[] args) { MatrizFibonacci base = new MatrizFibonacci(BigInteger.ONE,BigInteger.ZERO); Integer n = 1000; AlgoritmoConUnaSolucion<MatrizFibonacci> a = new PotenciaEnteraDyVImpl<MatrizFibonacci>(base,n); a.ejecuta(); mostrar(\"El problema es \"+n+\" la solucion \"+a.getSolucion().get(0,0)); } } El problema de la potencia entera puede ser instanciado para resolver otros problemas. Algunos de ellos son: • ܽ௡ con a de tipo entero o real. • ‫ܣ‬௡ con A una matriz rectangular • Una recurrencia del tipo ݂௡ ൌ ܽଵ݂௡ିଵ ൅ ‫ ڮ‬൅ ܽ௞݂௡ି௞. Con unas condiciones iniciales dadas. La idea se la misma que en el caso de Fibonacci: transformar la recurrencia en la ecuación matricial ݂௡ ܽଵ ܽଶ … ܽ௞ ݂௡ିଵ ቌ ݂௡…ିଵ ቍ ൌ ൭ 1… …0 …… …0 ൱ ቌ݂௡…ିଶቍ ݂௡ି௞ାଵ 0 0 … 0 ݂௡ି௞ y posteriormente calcular la potencia n-ésima de la matriz. • ܽ௡ % ‫ݎ‬. Es decir el resto con respecto a r de ܽ௡ sin tener que hacer la operación de potencia y usando resultados intermedios razonablemente pequeños. Esto es debido a las propiedades ܽଶ % ‫ ݖ‬ൌ ሺܽ % ‫ݖ‬ሻଶ % ‫ ݖ‬y ሺܾ ‫ܽ כ‬ሻ % ‫ ݖ‬ൌ ሺሺܾ%‫ݖ‬ሻ ‫ כ‬ሺܽ%‫ݖ‬ሻሻ%‫ ݖ‬que nos permite implementar el tipo BasePotenciaEntera con esas operaciones. Divide y Vencerás con Memoria La técnica de divide y vencerás tiene una variante muy importante. Es la técnica de Divide y Vencerás con Memoria. El problema de Fibonacci nos puede servir de nuevo de motivación. Hemos resuelto el problema de Fibonacci de dos maneras: mediante un enfoque directo usando Divide y Vencerás sin Memoria (la técnica de Divide y Vencerás que hemos usado hasta ahora Fichas 1, 2) e instanciando el problema de la Potencia Entera (Ficha 4). En la versión de las Ficha 1 (también de la 2) podemos comprobar que la complejidad es exponencial. Eso es debido a que al resolver el problema de f(n) se resuelven primero los f(n-1) y f(n-2). Estos a su vez resuelven primero f(n-2), f(n-3) y f(n-3), f(n-4) respectivamente y así sucesivamente. Vemos que para resolver f(n) se resuelven muchas veces muchos de los subproblemas. En particular el f(n-3) anterior. Una forma de evitar resolver el mismo problema varias veces es recordar que ya se resolvió y cuál fue la solución. El esquema general de esta técnica es:

݉ሺܺሻ, ‫݉ א ܺ ݅ݏ‬ ‫݁ݏܾܽ ݋ݏܽܿ ݊ݑ ݏ݁ ݅ݏ‬ ݂ሺܺሻ ൌ ቐ ܵ଴, ‫݋ݒ݅ݏݎݑܿ݁ݎ ݋ݏܽܿ ݊ݑ ݏ݁ ݅ݏ‬ ܿ‫ܣ‬ᇱ൫ܺ௔, ݂ሺܺଵ௔ሻ, ݂ሺܺଶ௔ሻ, … , ݂ሺܺ௞௔ሻ൯, ‫ ݏ‬ൌ ܿ‫ܣ‬ᇱሺ… ሻ ‫ ݏ ؠ‬ൌ ܿ‫ܣ‬ሺ… ሻ, ݉ ൌ ݉൅൏ ܺ, ‫ ݏ‬൐ Como vemos siempre aparece un nuevo caso base que ocurre si el problema considerado pertenece al dominio de la memoria. El nuevo operadores cA´ tiene que, además de calcular la solución a partir de las soluciones de los sub-problemas, añadir a la memoria la solución encontrada del problema. Donde la memoria m puede concretarse mediante una variable de tipo Esto puede hacerse con un Map<Problema,Solucion>. La forma de implementarlo es distinta según que representemos los problemas como objetos o como conjunto de parámetros. Veamos la primera alternativa en primer lugar. La ficha correspondiente sería: Ficha 5 Problema de Fibonacci Técnica: Divide y Vencerás con Memoria Representación: Cada problema un objeto Tamaño: N Propiedades Individuales N, Integer no negativo f(n) = { 0 Si n ==0 1 Si n == 1 f(n-1)+f(n-2) Si n > 1 Para implementar la información de la Ficha 5 podemos reutilizar la clase ProblemaFibonacciDyVImpl2 que usamos en la Ficha 1. Pero ahora necesitamos una clase que implemente el tipo Algoritmo con las ideas del método Divide y Vencerás con Memoria. Esta es la clase AlgoritmoDivideYVencerasConMemoria. Los detalles más relevantes de la misma son: public class AlgoritmoDivideYVencerasConMemoria<S> implements AlgoritmoConUnaSolucion<S> { private Map<ProblemaDyV<S>, S> map; private ProblemaDyV<S> problema; private S solucion; public AlgoritmoDivideYVencerasConMemoria(ProblemaDyV<S> p) { problema = p; map = MapsFactory.creaMap(); tipoDeAlgoritmo = Algoritmo.TipoDeAlgoritmo.DIVIDE_Y_VENCERAS_CON_MEMORIA; } public void ejecuta() { solucion = dYV(problema); }





















s = s+s1+s2; } s = n-1+s/n; map.put(n, s); } return s; } ... Tras resolver numéricamente la recurrencia representamos los valores obtenidos para T(n). En el gráfico vemos que es casi una recta pero al intentar ajustarla obtenemos un ܴଶ ൌ 0.9987. 180000 T(n) frente a n 160000 140000 y = 16,383x - 7446,5 120000 R² = 0,9987 100000 T(n) frente a n 80000 Lineal (T(n) frente a n) 60000 40000 5000 10000 15000 20000 0 0 Tal como vemos en la figura anterior el ajuste de T(n), aunque cercano, no es exactamente una recta. Representamos ahora T(n) frente a n*ln(n). Vemos que el ajuste es perfecto con ܴଶ ൌ 1.

180000 T(n) frente a n*ln(n) 160000 140000 y = 1,7344x - 987,83 120000 R² = 1 100000 T(n) frente a n*ln(n) 80000 Lineal (T(n) frente a 60000 n*ln(n)) 40000 20000 20000 40000 60000 80000 100000 0 0 Concluimos que la solución de la recurrencia anterior es . Estas ideas pueden usarse para otras recurrencias complejas. Cálculo del umbral Una cuestión importante en la técnica de Divide y Vencerás es la definición del tamaño que separa los casos base de los casos recursivos. Llamaremos umbral a ese tamaño. Un problema se considera simple (caso base) cuando su tamaño es menor o igual que el umbral elegido. Veamos como calcularlo. El tiempo de ejecución del algoritmo dependerá del umbral seleccionado. Sea un algoritmo del tipo Divide y Vencerás donde el coste de la solución directa (caso base) sea h(n) entonces el tiempo de ejecución verifica: El umbral óptimo se encontrará en la intersección entre el tiempo de ejecución del caso base (línea roja) y el del caso recursivo (línea azul): Sustituyendo en e igualando a la ecuación para el umbral es:

݄ܽሺܾ݊଴ሻ ൅ ݃ሺ݊଴ሻ ൌ ݄ሺ݊଴ሻ Ejemplo. Sea el algoritmo con la ecuación de recurrencia dada por: ܶሺ݊ሻ ൌ ൝ ݊ଶ ‫ ݅ݏ‬1 ൑ ݊ ൑ ݊଴ ݊ ‫ ݊ ݅ݏ‬൐ ݊଴ 3ܶ ቀ2ቁ ൅ 16݊ El umbral verifica 3 ሺ௡బሻଶ ൅ 16݊଴ ൌ ݊଴ଶ, ଷ௡బమ ൅ 16݊଴ ൌ ݊଴ଶ, 16݊଴ ൌ ଵ ݊଴ଶ, ݊଴ ൌ 8 que es el ସ ସ ଶ tamaño del umbral. Medición del tiempo de ejecución y otros parámetros de un algoritmo Junto al cálculo teórico de la complejidad es conveniente medir para implementación concreta el tiempo de ejecución y otros parámetros relevantes. Para ello diseñamos una clase denominada Metricas con ese objetivo. El tipo Algoritmo, que hemos visto arriba, dispone de una propiedad Metricas que nos permite medir sus parámetros particulares. public class Metricas { int getNumeroDeLLamadasRecursivas() {…} int getNumeroDeUsosDeLaMemoria(){…} long getTiempoDeEjecucion(){…} int getNumeroDeCasosBase(){…} long getNumeroDeProblemas(){…} ... } La clase Metricas está diseñada para medir, de un algoritmo dado, las siguientes propiedades, a las que añadiéremos otras más adelante. • NumeroDeLLamadasRecursivas: Número de llamadas recursivas. • NumeroDeUsosDeLaMemoria: Número de veces que se accede a • TiempoDeEjecucion: Tiempo de ejecución en nanosegundos. • NumeroDeCasosBase: Número de casos base resueltos. • NumeroDeProblemas: Número de problemas distintos resueltos. En el caso del problema de Fibonacci, resuelto por la técnica de Divide y Vencerás con Memoria y N = 1000, obtenemos los siguientes parámetros: Número de Llamadas Recursivas = 1999 Numero de Usos de la Memoria = 998 Tiempo de Ejecucion en nanoseg= 15 Número de Casos Base =2 Número de Problemas = 1001