Home Algoritmos y Estructuras de Datos (VJ1215)

Curso 2021/2022

5. Técnicas algorítmicas

Horas de clases presenciales: 14 (8 teoría + 6 prácticas)
Horas de trabajo no presencial: 28
Ratio: 4 horas no presenciales por cada clase de 2 horas

A este tema se le podría dedicar más tiempo en un curso de Algorítmica, pero nos ajustaremos al tiempo disponible en esta asignatura, contando mucho con las horas de trabajo no presencial.

5.1. Algoritmos voraces

Recursos

Como primer ejemplo de algoritmo voraz vamos a estudiar el algoritmo de Huffman, con el que realizamos también las prácticas del tema 4. Puedes encontrar la bibliografía recomendada en los recursos del tema 4.

En el tema 6 "Algoritmos fundamentales sobre grafos" veremos otros ejemplos de algoritmos voraces: el algoritmo de Dijkstra (problema del camino óptimo) y el algoritmo de Prim (problema del árbol de recubrimiento óptimo).

Ejercicios

  1. Clase de teoría TE1 14/10, TE2 19/10

    Aplica el algoritmo de Huffman con estos datos y dibuja el árbol de Huffman resultante:

    Carácterabcdefgh
    Frecuencia8030402070601050

    Calcula cuántos bits ahorramos empleando la codificación obtenida en vez de 3 bits por carácter.

  2. Los biólogos utilizan los caracteres A, C, G y T para denotar Adenina, Citosina, Guanina y Timina, respectivamente. De ese modo una secuencia de ADN queda representada como una secuencia formada por esos caracteres, por ejemplo GATTACA. Si cada carácter se codificase con 8 bits, una secuencia de longitud n ocuparía 8n bits. Teniendo en cuenta que solo hay 4 caracteres posibles, podríamos emplear 2 bits para codificarlos, reduciendo así a 2n la ocupación de una secuencia de n caracteres.

    1. Supongamos que sabemos que en el ADN hay un 40 % de Adenina, un 10 % Citosina, un 10 % de Guanina y un 40 % de Timina. ¿Sabrías utilizar esa información para reducir más la ocupación de las secuencias de ADN? Ilústralo obteniendo la codificación de cada carácter y calculando, con la codificación obtenida, cuál sería la ocupación de una secuencia de n caracteres que tenga esas frecuencias.
    2. ¿Qué relación tiene ese problema con los árboles binarios?
    3. ¿Qué relación tiene ese problema con las colas de prioridad?
    4. ¿Qué relación tiene ese problema con las estrategias algorítmicas?

    Solución

  3. Analiza el coste temporal en el peor caso del algoritmo de Huffman cuando se aplica a un alfabeto que tiene n caracteres, suponiendo que la cola de prioridad que utiliza el algoritmo se implementa empleando:

    1. Un vector no ordenado.

    2. Un vector ordenado.

    3. Un árbol binario de búsqueda.

    4. Un árbol AVL.

    5. Clase de teoría TE2 26/10, TE1 28/10

      Un montículo binario.

    6. Un montículo de Fibonacci.

    Un montículo de Fibonacci es una estructura de datos que permite implementar colas de prioridad con estos costes temporales:

    Coste en el peor caso Coste amortizado
    Insertar O(1) O(1)
    ConsultarMínimo O(1) O(1)
    EliminarMínimo O(n) O(log n)

    Solución

  4. Aplicando el algoritmo de Huffman hemos obtenido este resultado:

    Carácter a e i o u
    Código 0 10 110 1110 1111

    Propón una tabla de frecuencias a partir de la cual se haya podido obtener eso y dibuja el árbol de Huffman.

  5. Ejercicio opcional

    Para conocer otro ejemplo sencillo de aplicación de la estrategia voraz, lee el apartado 10.1.1 "A Simple Scheduling Problem" del capítulo 10 "Algorithm Design Techniques" del libro "Data Structures and Algorithm Analysis in C++" (2014) de M. A. Weiss. Intenta resolver el caso con P procesadores antes de leer su solución.

5.2. Divide y vencerás

Recursos

Complementa la clase de teoría estudiando los siguientes apartados del capítulo 7 "Sorting" y del capítulo 10 "Algorithm Design Techniques" del libro "Data Structures and Algorithm Analysis in C++" (2014) de M. A. Weiss.

  • 7.6 Mergesort
  • 10.2 Divide and conquer
    • 10.2.1 Running Time of Divide and Conquer Algorithms
    • 10.2.2 Closest-Points Problem

Debes aprender a aplicar el denominado Teorema Maestro tal como se formula en los teoremas 10.6 y 10.7 del apartado 10.2.1; entender las demostraciones de esos teoremas es opcional.

El Master Theorem Solver de Nayuki Minase te puede resultar de ayuda para comprobar tus soluciones.

Recursos en castellano y opcionales

En castellano, el algoritmo de ordenación por mezcla (Mergesort) lo puedes encontrar en el capítulo 8 "Algoritmos de ordenación" del libro "Estructuras de datos en Java" (2013) de M. A. Weiss.

Aunque no existe una traducción a castellano reciente del tema 10.2, puedes encontrarlo idéntico en el capítulo 10 "Técnicas de diseño de algoritmos" de la edición "Estructuras de datos y algoritmos" (1995) de M. A. Weiss. En esa edición los algoritmos están expresados en lenguaje Pascal, pero es fácil entenderlos.

Ejercicios

  1. Problema del par de puntos más cercanos

    Clase de prácticas LA1 y LA3 28/10, LA2 y LA4 02/11

    Imagina que estás desarrollando un videojuego en el que puede haber muchos objetos que tienen unas coordenadas 2D y debes encontrar los dos objetos más próximos entre si, por ejemplo para prevenir una posible colisión entre ellos (esto también tiene aplicación práctica en sistemas de control de tráfico aéreo) o para que esos dos personajes del videojuego sean los que luchen, se emparejen, etc.

    1. Ejercicio opcional

      Implementa en C++ una función que reciba un vector de n puntos en el plano y devuelva la distancia entre los dos puntos más cercanos empleando el algoritmo de fuerza bruta que calcula todas las distancias posibles con coste O(n2).

      Solución

      Código de prueba

    2. Resuelve el mismo problema del apartado a, empleando el algoritmo que emplea la estrategia Divide y Vencerás, cuyo tiempo de ejecución es O(n log n). Este algoritmo se explicará en clase de prácticas.

      Ayuda (resumen de lo discutido en clase)

      Puedes completar este programa de prueba TestClosestPoints.cpp para que produzca esta salida TestClosestPoints.salida.

      Ayuda con C++

      Si lo deseas puedes implementar y usar tu propia clase Punto, o también puedes hacer uso de la clase pair para representar puntos. Si optas por lo segundo, puedes emplear typedef para llamarle Punto:

      typedef pair<float, float> Punto;
      Punto p1 = {2, 3}, p2 = {5, 7};
      vector<Punto> puntos = {p1, p2, Punto(3, 4), Punto(4, 4), Punto(4, 4), Punto(5,7)};
      if (p1 == p2) ...
      if (p1 < p2) ...
      		    

      Puedes utilizar min para calcular el mínimo de dos o de varios valores: ejemplo_min_max.cpp.

      Para crear copias de vectores puedes mirar este otro ejemplo de uso de vector: ejemplo_vector_copiar.cpp.

      Para ordenar los vectores, mira este ejemplo de uso de sort: ejemplo_vector_ordenar.cpp.

      • Para una de las dos ordenaciones que hay que realizar, la clase pair ya se comporta exactamente como necesitas (gracias a que en ella han implementado operator<). Puedes ver un ejemplo aquí al final. Si en vez de utilizar pair has decidido implementar tu propia clase Punto, le puedes añadir el operator< como se muestra en ejemplo_vector_ordenar.cpp.

      • Para la otra ordenación, puedes darle a sort una función de comparación para que la utilice en vez del operator<, como se ilustra también en ejemplo_vector_ordenar.cpp (también puedes consultar el apartado "A Function Pointer as Comparison Function" del tutorial "STL Sort Comparison Function" de Shao Voon Wong).

      Solución

      Código de prueba

    3. Ejercicio opcional

      Realiza una comparación experimental de ambos algoritmos, midiendo sus tiempos de ejecución al aplicarlos a vectores de puntos generados aleatoriamente. Observa la importancia de seleccionar el algoritmo más eficiente cuando hay que trabajar con grandes cantidades de datos en poco tiempo.

      Solución

      Si no realizas la implementación, sería interesante que al menos veas y representes gráficamente los resultados. También sería interesante que representes gráficamente y compares estos resultados de 2014 y estos resultados de 2021. Observa que los tiempos se reducen al trabajar con una nueva CPU, un nuevo compiilador, etc., pero la forma de la curva se mantiene.

      Recuerda Para representar gráficamente los resultados puedes utilizar, por ejemplo, Gnuplot online: basta copiarlos en el panel "Data" y, si quieres, adaptar el contenido del panel "Plot script".

  2. Clase de teoría TE1 04/11, TE2 09/11

    Supongamos que queremos resolver el problema de encontrar el máximo en un vector de talla mayor que cero empleando la estrategia Divide y Vencerás. Analiza el coste temporal de las siguientes implementaciones, empleando el Teorema Maestro.

    Teorema Maestro
    1. Un primer programador ha realizado la siguiente implementación:

      int maximo(const vector<int> & v) { // Suponemos v.size() >= 1
         return maximo(v, 0, v.size() - 1);
      }
      int maximo(const vector<int> & v, int inicio, int fin) {
         if (inicio == fin)
            return v[inicio];
         else {
            int mitad = (inicio + fin) / 2;
            int maximoIzquierda = maximo(v, inicio, mitad);
            int maximoDerecha = maximo(v, mitad + 1, fin);
            if (maximoIzquierda >= maximoDerecha)
               return maximoIzquierda;
            else
               return maximoDerecha;
         }
      }
      		  

      Solución

    2. Un segundo programador hace lo que se muestra a continuación, en vez de trabajar con un solo vector como en el apartado a:

      int maximo(const vector<int> & v) { // Suponemos v.size() >= 1
         if (v.size() == 1) return v[0];
         int mitad = v.size() / 2;
         vector<int> izquierda(mitad);
         for (int i = 0; i < mitad; i++)
            izquierda[i] = v[i];
         vector<int> derecha(v.size() - mitad);
         for (int i = mitad, j = 0; i < v.size(); i++, j++)
            derecha[j] = v[i];
         int maximoIzquierda = maximo(izquierda);
         int maximoDerecha = maximo(derecha);
         if (maximoIzquierda >= maximoDerecha)
            return maximoIzquierda;
         else
            return maximoDerecha;
      }
      		  

      Solución

    3. Un tercer programador implementa el algoritmo utilizando un solo vector como en el primer apartado pero ahorrándose las variables maximoIzquierda y maximoDerecha, como se muestra a continuación:

      int maximo(const vector<int> & v) { // Suponemos v.size() >= 1
         return maximo(v, 0, v.size() - 1);
      }
      int maximo(const vector<int> & v, int inicio, int fin) {
         if (inicio == fin)
            return v[inicio];
         else {
            int medio = (inicio + fin) / 2;
            if ( maximo(v, inicio, medio) >= maximo(v, medio + 1, fin) )
      	 return maximo(v, inicio, medio);
            else
      	 return maximo(v, medio + 1, fin);
         }
      }
      		  

      Solución

    4. Un cuarto programador combina lo que hacen los dos anteriores:

      int maximo(const vector<int> & v) { // Suponemos v.size() >= 1
         if (v.size() == 1) return v[0];
         int mitad = v.size() / 2;
         vector<int> izquierda(mitad);
         for (int i = 0; i < mitad; i++)
            izquierda[i] = v[i];
         vector<int> derecha(v.size() - mitad);
         for (int i = mitad, j = 0; i < v.size(); i++, j++)
            derecha[j] = v[i];
         if (maximo(izquierda) >= maximo(derecha))
            return maximo(izquierda);
         else
            return maximo(derecha);
      }
      		  

      Solución

    5. Finalmente, un quinto programador propone lo siguiente:

      int maximo(const vector<int> & v, int inicio, int fin) { // Suponemos v.size() >= 1
         if (fin - inicio <= 3) {
            int aux = v[inicio];
            for (int i = inicio + 1; i <= fin; i++)
               aux = max(aux, v[i]);
            return aux;
         } else {
            int medio = (inicio + fin) / 2;
            int cuartoIzquierda = (inicio + medio) / 2;
            int cuartoDerecha = (medio + 1 + fin) / 2;
            int aux = maximo(v, inicio, cuartoIzquierda);
            aux = max(aux, maximo(v, cuartoIzquierda + 1, medio));
            aux = max(aux, maximo(v, medio + 1, cuartoDerecha));
            aux = max(aux, maximo(v, cuartoDerecha + 1, fin));
            return aux;
         }
      }
      int maximo(const vector<int> & v) {
         return maximo(v, 0, v.size() - 1);
      }
      		  

      Solución

  3. Mergesort

    1. Clase de teoría TE1 21/10, TE2 09/11

      Analiza el coste temporal del algoritmo de ordenación Mergesort empleando el Teorema Maestro.

    2. ¿Cómo cambiaría el tiempo de ejecución del algoritmo de ordenación Mergesort si la subrutina empleada para mezclar dos vectores ordenados tuviese un coste temporal O(n log n) en vez de O(n)?

    3. ¿Y si esa subrutina tuviese un coste temporal O(n2)?

    Solución

  4. Búsqueda binaria

    Utiliza el Teorema Maestro para analizar esta implementación de la búsqueda binaria recursiva que vimos en el tema 1.

    int busquedaBinariaRecursiva(const vector<int> & v, int dato, int inicio, int fin) {
       if (inicio <= fin) {
          int medio = (inicio + fin) / 2;
          if (v[medio] < dato)
             return busquedaBinariaRecursiva(v, dato, medio + 1, fin);
          else if (v[medio] > dato)
             return busquedaBinariaRecursiva(v, dato, inicio, medio - 1);
          else
             return medio;
       }
       return -1;
    }
    
    
    int busquedaBinariaRecursiva(const vector<int> & v, int dato) {
       return busquedaBinariaRecursiva(v, dato, 0, v.size() - 1);
    }
    	      

    Solución

  5. Exponenciación binaria

    1. El algoritmo de exponenciación binaria, que vimos en el ejercicio 10 del tema 1, es también un ejemplo de aplicación de la estrategia Divide y Vencerás. Considera la siguiente versión del algoritmo. Expresa su coste temporal empleando una relación de recurrencia y obtén su solución empleando el Teorema Maestro.

      float potencia(float x, int n) {
      
         if (n == 0)
            return 1;
      
         float y = potencia(x, n / 2);
      
         if (n % 2 == 1)
            return x * y * y;
      
         return y * y;
      
      }
      		  

      Solución

    2. Utiliza el Teorema Maestro para analizar cómo cambiaría el tiempo de ejecución si resolviésemos así el mismo problema:

      float potencia(float x, int n) {
      
         if (n == 0)
            return 1;
      
         if (n % 2 == 1)
            return x * potencia(x, n / 2) * potencia(x, n / 2);
      
         return potencia(x, n / 2) * potencia(x, n / 2);
      
      }
      		  

      Solución

  6. Encuentra la solución de las siguientes relaciones de recurrencia empleando el Teorema Maestro.

    1. T(n) = 7 T(n/2) + O(n2)
    2. T(n) = 8 T(n/2) + O(n2)
    3. T(n) = 8 T(n/4) + O(n2)
    4. T(n) = 4 T(n/2) + O(n2)

    Después comprueba tus soluciones empleando el Master Theorem Solver de Nayuki Minase.

    Recursos opcionales
    Algoritmo de Strassen para multiplicar dos matrices
    Opcionalmente, busca en el libro "Data Structures and Algorithm Analysis in C++" (2014) el apartado 10.2.4 (páginas 498-500 de la edición internacional, la que tiene la biblioteca de la UJI). Ahí se explica el algoritmo de Strassen para multiplicar matrices, cuyo tiempo de ejecución cumple la relación de recurrencia del apartado (a). En castellano puedes encontrar eso mismo en la edición "Estructuras de datos y algoritmos" (1995), páginas 394-397.

  7. Encuentra la solución de las siguientes relaciones de recurrencia empleando el Teorema Maestro.

    1. T(n) = T(n/2) + O(1)
    2. T(n) = 2 T(n/2) + O(1)
    3. T(n) = 4 T(n/4) + O(1)

    Después comprueba tus soluciones empleando el Master Theorem Solver de Nayuki Minase.

    Piensa algoritmos recursivos cuyo tiempo de ejecución se corresponda con esas relaciones.

  8. Encuentra la solución de las siguientes relaciones de recurrencia empleando el Teorema Maestro.

    1. T(n) = 2 T(n/2) + O(log n)
    2. T(n) = T(n/2) + O(log n)
    3. T(n) = T(n/2) + O(n log n)

    Después comprueba tus soluciones empleando el Master Theorem Solver de Nayuki Minase.

    Prueba tú mismo otros ejemplos si lo consideras conveniente, hasta saber aplicar bien el teorema.

  9. Ejercicio opcional

    Algoritmo de Karatsuba para multiplicar enteros

    El algoritmo de Karatsuba resuelve el problema de multiplicar números enteros de muchos dígitos. Para ello emplea la estrategia Divide y Vencerás. Estudia la explicación que puedes encontrar en el apartado 10.2.4 del libro "Data Structures and Algorithm Analysis in C++" (2014), hasta entender el cambio que hace que el tiempo de ejecución pase de T(n)=4T(n/2)+O(n) a T(n)=3T(n/2)+O(n).

    Resuelve ambas relaciones de recurrencia empleando el Teorema Maestro y compara sus resultados.

    En castellano puedes encontrar eso mismo en la edición "Estructuras de datos y algoritmos" (1995), páginas 393-394.

5.3. Programación dinámica

Recursos

En este tema partiremos de las explicaciones dadas en clase de teoría. Estudia este tema resolviendo los ejercicios propuestos. Tras intentar cada ejercicio, estudia su solución y pasa a intentar el siguiente. La bibliografía a consultar se irá indicando cuando sea necesario en los ejercicios.

Este es un tema complicado, no pretendas aprenderlo en un día, dedícale tiempo suficiente hasta la fecha de evaluación. Este curso vamos a dedicarle tres horas de clase de teoría y dos sesiones de prácticas. Intenta seguir el ritmo de esas clases.

Si no puedes asistir a la primera clase de teoría de este tema, empieza estudiando el apartado 7.6 "Programación Dinámica" del libro "Estructuras de datos en Java" (2013) de M. A. Weiss. A lo que se explica ahí añadiremos en este curso algoritmos recursivos eficientes y más ejemplos, como irás viendo en los ejercicios.

Ejercicios

Completa los siguientes ejercicios de forma no presencial. Incluso los que se hayan discutido en clase, resuélvelos de nuevo escribiendo tú la solución completa.

Nivel de dificultad 0

  1. Clase de teoría TE1 28/10, TE2 02/11

    Este es un ejercicio preliminar para entender el uso de una tabla para guardar resultados y no repetir cálculos.

    En el tema 1 hemos visto lo ineficiente que es calcular el n-ésimo número de Fibonacci de forma recursiva como sigue:

    long long fibonacci(int n) {
    
       long long resultado;
    
       if (n <= 1)
          resultado = n;
       else
          resultado = fibonacci(n - 1)
    	          + fibonacci(n - 2);
    
       return resultado;
    
    }
    	      

    Partiendo de esa versión, resuelve el problema de la ineficiencia añadiendo una tabla de resultados para no repetir cálculos. Después modifíca la implementación para rellenar la misma tabla de forma no recursiva.

    Solución

    La animación Dynamic Programming (Fibonacci) de David Galles te puede ayudar a entender la solución. Lo que denomina "Fibonacci Memoized" es la soluión recursiva eficiente y lo que denomina "Fibonacci Table" es la solución no recursiva eficiente.

El objetivo fundamental de este tema es que seas capaz de resolver ejercicios como los que se proponen a continuación. No solo por la enorme importancia del tema, también porque es un tipo de ejercicios que aparece en entrevistas de trabajo de programación. Para cada ejercicio, procede en este orden:

  1. Diseña una solución recursiva del problema (esa es normalmente la mayor dificultad).

    Tras intentarlo, consulta el enlace "Ayuda: solución recursiva inicial" en caso de que lo incluya el ejercicio.

    En las clases de teoría y prácticas también discutiremos la solución recursiva inicial de algunos de los ejercicios propuestos.

    En el "Código de prueba" que se proporciona, implementa esa solución recursiva en C++ como "Versión 1".

  2. Obtén a partir de ahí un algoritmo recursivo eficiente, añadiendo una tabla para guardar resultados y no repetir cálculos.

    En el "Código de prueba" que se proporciona, impleméntalo en C++ como "Versión 2".

    Recuerda cómo se pasó de la versión 1 a la versión 2 en fibonacci.cpp.

  3. Conviértelo en un algoritmo no recursivo eficiente, pensando en qué orden puede rellenarse la tabla anterior.

    En el "Código de prueba" que se proporciona, impleméntalo en C++ como "Versión 3".

    Recuerda cómo se pasó de la versión 2 a la versión 3 en fibonacci.cpp.

  4. Analiza el coste temporal y espacial de los algoritmos ii y iii.

Nivel de dificultad 1

  1. Clase de teoría TE1 28/10, TE2 02/11

    Considera un juego en el que cada partida tiene un diseño como el que ilustra el ejemplo de la siguiente figura.

    Matriz de celdas con puntuaciones

    El escenario siempre está formado por una matriz rectangular de celdas. Los números indican los puntos que el jugador puede acumular superando retos en cada celda. Las dimensiones de la matriz y las puntuaciones pueden variar de una partida a otra, pero las reglas del juego son siempre las siguientes:

    • El jugador debe empezar en la celda de la esquina superior izquierda y debe llegar hasta la celda de la esquina inferior derecha.

    • Solo se permiten dos tipos de movimientos para desplazarse de una celda a otra: hacia la derecha y hacia abajo.

    • No está permitido retroceder, salir de la frontera exterior ni atravesar las celdas negras.

    Diseña e implementa un algoritmo eficiente que, a partir de la matriz puntos correspondiente a una partida, calcule la máxima cantidad de puntos que puede acumular el jugador. En la matriz puntos las celdas no atravesables (celdas negras) se representarán con valor -1 y el resto de datos indicarán la cantidad de puntos que el jugador puede obtener en cada celda.

    Como sugerencia, empieza resolviendo el problema ignorando las celdas negras y después piensa qué hacer con ellas en la solución.

    Completa este código de prueba.

    Solución 1: hasta la última celda

    Solución 2: desde la última celda

    Costes

  2. Weighted interval scheduling

    Clase de prácticas LA1 y LA3 04/11, LA2 y LA4 09/11

    En una competición de videojuegos se programan n partidas. Para i desde 0 hasta n - 1, la partida i-ésima tiene una hora de inicio competición[i].inicio, una hora de finalización competición[i].final y un premio para el ganador competición[i].premio. Los premios son valores positivos. Los datos están ordenados de menor a mayor por hora de inicio. Un jugador tiene que decidir en qué partidas participa con el objetivo de maximizar la suma de los premios ganados y con la restricción de que no puede inscribirse en partidas cuyos horarios se solapan. Como ayuda, competición[i].primeraPosterior indica cuál es la primera de las partidas en las que podría participar después de participar en la i-ésima (si vale -1 indica que no hay ninguna). Por ejemplo, con los siguientes datos podría acumular 14000 ganando las partidas 1, 2 y 5, y el valor máximo que puede acumular es 15000 ganando las partidas 0 y 4:

    partida012345
    inicio101113151617
    final141217171918
    premio700030009000500080002000
    primeraPosterior3255-1-1

    Diseña e implementa un algoritmo eficiente para averiguar, dada una tabla competición como la que ilustra el ejemplo anterior, cuál es la máxima suma de premios que puede acumular un jugador (puedes utilizar de la tabla los datos que quieras).

    Completa este código de prueba.

    Ayuda: solución recursiva inicial

    Solución

    Costes

  3. House robber

    Clase de teoría TE2 02/11

    [Este es un ejemplo de ejercicio planteado por Google en sus entrevistas para seleccionar programadores.]

    A lo largo de una calle hay n casas, numeradas de 0 a n - 1. La casa i está pegada a la casa i - 1 por la izquierda y a la i + 1 por la derecha, para i = 1, ..., n - 2. Un ladrón va a robar lo máximo que pueda en estas casas, pero no puede robar en dos casas que estén pegadas porque el dueño de una casa robada avisará a sus vecinos izquierdo y derecho. Sea valoresCasas un vector de talla n en el que valoresCasas[i] es el valor que puede conseguir robando la casa i-ésima, para i = 0, ..., n - 1.

    Diseña e implementa un algoritmo eficiente que permita averiguar, dado valoresCasas, cuál es el máximo valor que puede acumular el ladrón.

    Por ejemplo, si hay cuatro casas con valoresCasas = {3000, 6000, 7000, 5000}, el valor máximo que puede acumular es 11000 robando las casas 1 y 3. Con valoresCasas = {6000, 10000, 3000, 15000, 4000, 2000, 8000, 5000} el resultado sería 33000, robando 10000, 15000 y 8000.

    Completa este código de prueba.

    Ayuda: solución recursiva inicial

    Solución

    Costes

  4. House coloring

    A lo largo de una playa hay n ≥ 1 casas, numeradas de 0 a n - 1. La casa k está pegada a la casa k - 1 por la izquierda y a la k + 1 por la derecha, para k = 1, ..., n - 2. Queremos pintar cada casa de un color de modo que no haya dos casas pegadas que tengan el mismo color, y podemos elegir entre tres colores. Nos dan una matriz de valores reales positivos costePintura en la que costePintura[c][k] es el coste de pintar de color c la casa k, para c = 0, ..., 2 y para k = 0, ..., n - 1.

    Diseña e implementa un algoritmo eficiente que calcule cuál es el mínimo coste total de pintar todas las casas. La cantidad de casas será uno de los datos de entrada al algoritmo, a diferencia de la cantidad de colores, que es constante y vale 3.

    Por ejemplo, con los siguientes datos:

    casas
    0123456
    030060020010001500500900
    colores140016004007001200400200
    25001300600100300500800

    el resultado sería 3300, correspondiente a elegir las siguientes celdas coloreadas:

    casas
    0123456
    030060020010001500500900
    colores140016004007001200400200
    25001300600100300500800

    Completa este código de prueba.

    Ayuda: solución recursiva inicial

    Solución (implementación A)

    Solución (implementación B)

    Costes

    Busca errores

    Solución alternativa, propuesta por una estudiante

  5. Clase de teoría TE1 04/11, TE2 09/11

    En las orillas de un rio hay n ≥ 3 aldeas, numeradas de 0 a n - 1 en el sentido de la corriente. Para desplazarnos de una aldea a otra podemos alquilar una barca, con la que solamente podemos navegar rio abajo. Nuestro objetivo es llegar desde la primera aldea hasta la última con coste mínimo. Podemos hacer escalas en otras aldeas si nos interesa.

    Para seguir viaje desde la aldea i, tenemos a lo sumo dos opciones:

    1. alquilar una barca que nos lleve desde la aldea i hasta la i + 1 con coste paseoCorto[i], o

    2. alquilar una barca que nos lleve desde la aldea i hasta la i + 2 (si existe) con coste paseoLargo[i].

    1. Diseña e implementa un algoritmo eficiente que, a partir de los vectores paseoCorto y paseoLargo, calcule el mínimo coste de ir desde la primera aldea hasta la última.

      Completa este código de prueba.

      Ayuda: solución recursiva inicial

      Solución 1: hasta la última aldea

      Solución 2: desde la primera aldea

      Costes

    2. Añade a cualquiera de las soluciones del apartado anterior lo que creas conveniente para mostrar la secuencia de aldeas por las que se pasa en el viaje de mínimo coste, tanto en la versión 2 como en la versión 3.

      Solución

Nivel de dificultad 2

  1. Clase de teoría TE1 18/11, TE2 16/11

    Resuelve este ejercicio después de completar el anterior.

    [Fuente: problema 8.32, página 315, del libro "Fundamentos de Algoritmia" (1997) de Gilles Brassard y Paul Bratley]

    En las orillas de un rio hay n ≥ 3 aldeas, numeradas de 0 a n - 1 en el sentido de la corriente. Para desplazarnos de una aldea a otra podemos alquilar una barca, con la que solamente podemos navegar rio abajo. Nuestro objetivo es llegar desde la primera aldea hasta la última con coste mínimo. Podemos hacer escalas en otras aldeas si nos interesa.

    Para seguir viaje desde la aldea i, podemos alquilar una barca que nos lleve a cualquier aldea j > i con coste costeAlquiler[i][j] ≥ 0.

    Diseña e implementa un algoritmo eficiente que, a partir de la información de la matriz costeAlquiler, calcule el mínimo coste de ir desde la primera aldea hasta la última.

    Completa este código de prueba.

    Ayuda: solución recursiva inicial

    Solución 1: hasta la última aldea

    Solución2: desde la primera aldea

    Busca errores

    Costes

  2. Coin change

    Clase de prácticas LA1 y LA3 11/11, LA2 y LA4 16/11

    Los habitantes de un lejano país disponen de n tipos de monedas, cuyos valores son valoresMonedas[1], valoresMonedas[2], ..., valoresMonedas[n]. Dichos valores son enteros positivos. Tenemos que averiguar cuál es la mínima cantidad de monedas necesaria para sumar exactamente el valor deuda, suponiendo que disponemos de cantidad suficiente de monedas de todos los tipos. El objetivo siempre se puede conseguir, gracias a que existen monedas cuyo valor es 1.

    Por ejemplo:

    • Si valoresMonedas = {5, 21, 1, 25} y deuda = 63 entonces la solución sería 3, correspondiente a coger 3 monedas de valor 21 para sumar 63.

      Observa que ese resultado no es el que obtendría un algoritmo voraz que empiece devolviendo la máxima cantidad posible de la moneda más grande (en este ejemplo, dos monedas de 25), después de la siguiente, y así sucesivamente (así cogeríamos 2 monedas de 25, 2 de 5 y 3 de 1, en total 7 monedas). Ese algoritmo no resolvería correctamente el problema.

    • Con valoresMonedas = {5, 21, 1, 25} y deuda = 65 la solución sería 5, correspondiente a coger 2 monedas de valor 25 y 3 de valor 5 para sumar 65, o bien a coger 3 monedas de valor 21 y 2 de valor 1.

    • Con valoresMonedas = {1, 4, 6, 10} y deuda = 22 la solución sería 3, correspondiente a 22 = 10 + 6 + 6

      Observa que ese resultado es mejor que devolver 4 monedas sumando 22 = 10 + 10 + 1 + 1 o 22 = 6 + 6 + 6 + 4. La solución óptima no se construye con la máxima cantidad posible de monedas de 10 o la máxima cantidad posible de monedas de 6 o la máxima cantidad posible de monedas de 4 o la máxima cantidad posible de monedas de 1.

    1. Diseña e implementa un algoritmo eficiente que, dados deuda y el vector valoresMonedas, calcule la mínima cantidad de monedas que suman deuda.

    2. Modifica la implementación para que muestre en la salida estándar las monedas correspondientes a la solución del apartado anterior (en caso de empate entre varias soluciones, mostrará una cualquiera de ellas).

    Completa este código de prueba. Cuando veas que la versión 1 tarda mucho en obtener el quinto resultado, puedes interrumpirla y repetir la prueba con la versión 2.

    Ayuda: solución recursiva inicial

    Solución (compara de nuevo la versión 1 con la 2 y la 2 con la 3 para ver cómo se ha pasado de una a otra con las transformaciones mínimas necesarias)

    Costes

  3. 0/1 knapsack - mochila 0/1

    En un centro comercial nos ha tocado un premio que consiste en que nos podemos llevar los objetos que queramos con la única restricción de que la suma de sus pesos no supere pesoMáximo. De cada uno de los n objetos que hay en el centro comercial, hay disponible una sola unidad, que es indivisible. Para i = 0, 1, ..., n - 1, el objeto i-ésimo tiene un peso peso[i] y un valor valor[i]. Tanto pesoMáximo como los pesos de los objetos son enteros positivos.

    Diseña e implementa un algoritmo eficiente para averiguar, a partir de los datos anteriores, cuál es la suma de valores máxima que podemos conseguir sin que la correspondiente suma de pesos supere pesoMáximo.

    Por ejemplo, con los siguientes datos:

    objeto0123
    peso100405080
    valor5000360045008000

    y con pesoMáximo = 100, el resultado sería 8100, que corresponde a elegir los objetos 1 y 2, cuyo peso suma 90. Observa que no necesariamente nos interesa elegir el objeto de mayor peso, el de mayor valor, o el de mayor valor por unidad de peso.

    Completa este código de prueba (incluye más ejemplos).

    Ayuda: solución recursiva inicial

    Solución

    Costes

  4. Unbounded knapsack

    Resuelve el ejercicio 10 de este examen.

    Completa este código de prueba.

    Solución

    Costes

  5. Rod cutting

    Resuelve el ejercicio 5 de este examen parcial.

    Completa este código de prueba.

    Ayuda: solución recursiva inicial

    Solución 1

    Costes

  6. Assembly line scheduling

    Resuelve el ejercicio 1 de este examen parcial.

    Completa este código de prueba.

    Ayuda

    Solución 1: hasta la última etapa

    Solución 2: desde la primera etapa

    Costes

Opcionalmente, en las evaluaciones de cursos anteriores puedes encontrar más ejercicios de este tema si quieres seguir practicando.

Nivel de dificultad 3

Los siguientes ejercicios son opcionales y no van para examen. Son propios de asignaturas que tienen más créditos para este tema. En ellos la dificultad del problema es mayor y, por ello, no se pretende que seas capaz de encontrar la solución recursiva inicial. El objetivo es que, una vez entendida consultando la bibliografía, seas capaz de programarla eficientemente aplicando lo que has aprendido hasta ahora.

  1. Ejercicio opcional

    Longest common subsequence (LCS)

    Sean dos secuencias A = A1A2...An y B = B1B2...Bm, formadas por elementos de un alfabeto finito dispuestos en un determinado orden. Una subsecuencia es el resultado de eliminar cero o más elementos de una secuencia, manteniendo el orden de los elementos restantes.

    Necesitamos un algoritmo eficiente para, dadas dos secuencias cualesquiera A y B, calcular la longitud de la subsecuencia común de A y B más larga posible.

    Por ejemplo, dadas A = barcelona y B = valencia:

    • ael es subsecuencia de A pero no es subsecuencia de B.

    • alena es subsecuencia de B pero no es subsecuencia de A.

    • Una subsecuencia común de A y B es aea, de longitud 3.

    • Otras subsecuencias comunes de A y B, más largas que aea, son aena y alna, de longitud 4.

    • Como no hay subsecuencias comunes más largas que esas, el resultado buscado sería 4.

    Puedes encontrar una solución recursiva para ese problema en estos apartados de la Wikipedia:

    Tras entender esa solución recursiva, como ejercicio (a) escribe un algoritmo recursivo que resuelva el problema eficientemente empleando Programación Dinámica, (b) después conviértelo en un algoritmo que calcule lo mismo de forma no recursiva, y (c) analiza el coste temporal y espacial de ambos.

    Solución (pseudocódigo)

  2. Ejercicio opcional

    Sequence alignment

    Para ver otro ejemplo importante de aplicación de la Programación Dinámica, lee el apartado 3.7 "Sequence Alignment" del libro "Foundations of Algorithms" (2015) de R. E. Neapolitan.

    Tras entender las explicaciones, como ejercicio (a) escribe un algoritmo recursivo que resuelva el problema eficientemente empleando Programación Dinámica, (b) después conviértelo en un algoritmo que calcule lo mismo de forma no recursiva, y (c) analiza el coste temporal y espacial de ambos.

    Solución (pseudocódigo)

  3. Ejercicio opcional

    Chained matrix multiplication

    El apartado 3.4 "Chained Matrix Multiplication" del libro "Foundations of Algorithms" (2015) de R. E. Neapolitan explica otro ejemplo importante de aplicación de la Programación Dinámica.

    Alternativamente, puedes encontrar una descripción diferente del mismo tema en el apartado 10.3.2 "Ordering Matrix Multiplications" del capítulo 10 "Algorithm Design Techniques" del libro "Data Structures and Algorithm Analysis in C++" (2014) de M. A. Weiss.

    En castellano puedes encontrar lo mismo (excepto el código C++) en el capítulo 10 "Técnicas de diseño de algoritmos" del libro "Estructuras de datos y algoritmos" (1995) de M. A. Weiss.

5.4. Búsqueda con retroceso

Recursos

En este tema nos basaremos en los siguientes apartados del capítulo 5 "Backtracking" del libro "Foundations of Algorithms" (2015) de R. E. Neapolitan:

  • 5.1 The Backtracking Technique
  • 5.2 The n-Queens Problem
  • 5.4 The Sum-of-Subsets Problem
  • 5.5 Graph Coloring

Ejercicios

Resuelve los siguientes ejercicios tras completar los del tema 6.

  1. Problema de las N reinas - N queens

    Clase de teoría TE1 16/12, TE2 21/12

    1. Utiliza la animación Recursive N-Queens de David Galles paso a paso con n = 4, y entiende el algoritmo con su ayuda (hay una errata: el último "=" debe ser un "-"). Dibuja los nodos del árbol del espacio de estados que se visitan en profundidad hasta encontrar una solución.

    2. A continuación se proporcionan tres implementaciones en C++ equivalentes. Siguiendo la nomenclatura del libro "Foundations of Algorithms" (2015) de R. E. Neapolitan:

      • nreinas-Neapolitan-checknode.cpp se corresponde con el esquema denominado checknode:

        void checknode(node v) {
        
            node u;
        
            if (promising(v))
                if (there is a solution at v)
                    write the solution;
                else
                    for (each child u of v)
                        checknode(u);
        
        }
        		      
      • nreinas-Neapolitan-expand.cpp se corresponde con el esquema denominado expand:

        void expand(node v) {
        
            node u;
        
            for (each child u of v)
                if (promising(u))
                    if (there is a solution at u)
                        write the solution;
                    else
                        expand(u);
        
        }
        		      
      • nreinas-DavidGalles.cpp es intermedia entre ambas y se asemeja más a lo que muestra David Galles en su animación, con dos diferencias: la animación hace por columnas lo que en esa versión se hace por filas, y la animación busca la primera solución y devuelve true al encontrarla mientras que esa versión muestra todas las soluciones posibles.

      Asegúrate de que las entiendes. ¿Qué función se corresponde en esas implementaciones con la que en los esquemas se denomina promising?

    3. [Fuente: ejercicio 7, página 245, del libro "Foundations of Algorithms" (2015) de R. E. Neapolitan]

      Tanto la animación como las tres implementaciones anteriores realizan un bucle en la función que comprueba que no hay conflictos. ¿Cómo podemos eliminar ese bucle y hacer que esa función se ejecute en tiempo O(1)?

      Ayuda

      Solución: Mira la página 28 de estas transparencias "Recursion and Recursive Backtracking" de D. G. Sullivan.

      Implementacion

  2. Graph coloring

    Ejemplo de grafo coloreado

    Queremos asignar un color a cada vértice de un grafo no dirigido, de modo que todo arco del grafo conecte vértices de colores diferentes. Hay un máximo de k colores disponibles, numerados entre 1 y k.

    Solo necesitamos una solución, o saber que no existe ninguna.

    Diseña un algoritmo para resolver ese problema, empleando búsqueda con retroceso.

    Añade a la clase GrafoNodirigido del tema 6 un método público

    vector<int> colorearGrafo(int cantidadDeColores) const;
    	      

    que devuelva como resultado un vector en el que la posición i contenga el color asignado al vértice i, o lance una excepción indicando que con esa cantidad de colores no existe solución.

    Pruébalo con el grafo ejemploIslas.gr del ejercicio 24 del tema 6, y después modifica el grafo para conseguir que no sea 2-coloreable ni 3-coloreable.

    Ejemplo de grafo islas coloreado

    Ayuda

    Solución

    Probar la solución

  3. Problema del caballo - Knight's tour

    1. Diseña un algoritmo para resolver la siguiente versión del problema del recorrido del caballo de ajedrez utilizando búsqueda con retroceso: dada la posición inicial de un caballo de ajedrez en un tablero con n × m casillas, encontrar un recorrido formado por n·m - 1 saltos consecutivos que permita al caballo visitar todas las casillas del tablero sin repetir ninguna.

      Solo necesitamos una solución, o saber que no existe ninguna.

      La solución será una matriz de dimensiones n × m en la que cada celda contenga el número de orden en que es visitada. Por ejemplo:

      14710
      12925
      36118

      En caso de no existir solución, hay que detectarlo e indicarlo lanzando una excepción. Esto sucede, por ejemplo, con un tablero de 4 × 4 empezando en (0,0).

      Implementa en C++ el algoritmo:

      vector<vector<int> > problemaCaballo(int filas, int columnas, int filaInicial, int columnaInicial);
      		  

      Ayuda

      Solución

      Probar la solución

    2. Modifica la implementación del apartado a para que muestre y cuente todos los recorridos del caballo válidos que existan, en vez de mostrar solamente el primero que encuentre y terminar.

      Solución

      Probar la solución

    3. Modifica la implementación del apartado b para resolver esta variante del problema: dado un tablero con n × m casillas, encontrar todos los recorridos formados por n·m saltos consecutivos que permitan al caballo visitar todas las casillas del tablero sin repetir ninguna y terminar en la misma casilla en la que empezó.

      Es decir, se trata ahora de buscar ciclos (recorridos cerrados) en vez de recorridos abiertos.

      void cicloCaballo(int filas, int columnas);
      		  

      Solución

      Probar la solución