Problema de selección de actividades

 

Planteamiento: dado un conjunto de n intervalos de la forma [a_i,b_i], 0 ≤ a_i < b_i≤2,000,000,000 encontrar un subconjunto de ellos de tamaño máximo de tal forma que la intersección de cada par sea vacía (es decir, que ningún par se “traslape”).

 

Clasificacion	Fuerza bruta	D.P. / Memorización	Glotón (óptimo)
Límites razonables	1<=n<=40	1<=n<=5,000	1<=n<=100,000
Complejidad en tiempo	O(2n)	O(n2)	O(n log n)
Complejidad en memoria	O(n)	O(n)	O(n)
Nivel OIEG	Avanzado	Avanzado	Avanzado
Nivel OMI	Normal	Normal	Normal
Nivel IOI	Básico	Básico	Básico

 

Dentro de los algoritmos “glotones”, éste es quizá el más conocido y el que más se utiliza como ejemplo para ilustrar las ideas detrás de esta clase de algoritmos. Puedes encontrar más sobre este problema si buscas “Event Scheduling Problem” (problema de selección de eventos, o algo así). La variable importante es el número de intervalos, n.

 

Puedes imaginarte el proceso de “buscar la solución” como un proceso en el que vas decidiendo, para cada intervalo, si lo tomas o lo dejas. Recuerda que como todo “proceso” debes hacer todo organizadamente. Dependiendo de cómo tomes las decisiones, puedes llegar a alguna de las siguientes soluciones (podrías llegar a otra solución completamente diferente, claro!).

 

Fuerza bruta:

 

            Algo que ayuda mucho es imaginar que estás en una situación y ver qué consecuencias tendrá el que tomes cada una de las posibles decisiones, es decir, dado que estás en una situación X a partir de la cual puedes tomar alguna de las decisiones D₁, D₂, ...D_k, a qué situaciones te conducirá cada decision, digamos Y₁, Y₂, ..., Y_k . Si logras determinar cuál de todas estas situaciones es la mejor simplemente tomas la decisión que te conduzca a esa situación. Supongamos que el primer intervalo que eliges (el que inicia más a la izquierda, digamos) es [a_k,b_k], entonces el siguiente intervalo que elijas [a_i,b_i] debe cumplir que b_k ≤ a_i es decir, debe empezar al terminar el primer intervalo o después. Esta simple condición nos lleva a diseñar nuestra primera solución: supongamos que el último de todos los intervalos que hemos elegido termina en

T, ahora tenemos un conjunto de posibles decisiones que podemos tomar: para cada uno de los intervalos que empiecen en T o después de T, {[a_j,b_j]} podemos decidir que ése sea el siguiente intervalo elegido. Si elegimos el intervalo [a_j,b_j] eso nos lleva a una situación en la que T=b_j la cual es una situación similar a la

anetrior.

 

int maxIntervalos ( int T)//0<=T<=2,000,000,000

   {

      int mejorOpcion=0;

      REP (i, n)

         if(T<=intervalos[i].inicio)//podemos elegir este intervalo            

            {

               int opcion=1+maxIntervalos(intervalos [i].final);

               if(opcion>mejorOpcion)

                  mejorOpcion=opcion;

            }      

      return mejorOpcion;

   }

Memorización:

Para memorizar las soluciones que se van calculando necesitamos un areglo de tamaño 2,000,000,001 (necesitamos espacio para cada posible valor de T), esto claramente no es posible, pero no es difícil darse cuenta de que a lo más habrá n diferentes valores de T con n<<T. La siguiente idea surge inmediatamente, en lugar de usar T usaremos el índice del último intervalo elegido k.

 

int maxIntervalos ( int k)//0<=k< n

   {

      int T= intervalos[k].final;

      int mejorOpcion=0;

      REP (i, n)

         if(T<=intervalos[i].inicio)             

             {

                 int opcion=1+maxIntervalos(i);

                 if(opcion>mejorOpcion)

                    mejorOpcion=opcion;

             }      

         return mejorOpcion;

     }

Ahora para memorizar solamente necesitamos un arreglo de tamaño n.

 

int cache[n];

int maxIntervalos( int k)   

   { 

      if (cache[k]>=0)

         return cache[k];

      int T=intervalos[k].final, mejorOpcion=0;

      REP (i, n)

         if(T<=intervalos[i].inicio)             

            {

               int opcion=1+maxIntervalos(i);

               if(opcion>mejorOpcion)

                  mejorOpcion=opcion;

            }      

      return cache[k]=mejorOpcion;

   }

 

Programación Dinámica:

 

Para usar programación dinámica necesitamos encontrar en qué orden debemos llenar la tabla de soluciones (“cache” en el ejemplo anterior) de tal forma que cuando calculemos uno de los elementos de la matriz, todas las soluciones de las cuales depende ya estén calculadas. Este problema puede ser muy difícil de resolver por lo que uno a veces se pregunta “¿por qué preocuparme del orden en el que debe llenarse la matriz si la memorización lo hace por mi?”, bueno, hay algunos casos en los que el número de llamadas recursivas (mas bien, el nivel de la recursión) es tan alto que la memoria destinada a guardar las llamadas recursivas (el “stack”) se llena (en este caso se dice que “la pila se desborda”, “stack overflow”) y por tanto aunque haya suficiente memoria para guardar los resultados parciales, la solución por memorización falla. Al usar programación dinámica no debemos preocuparnos por la pila, ya que no hacemos llamadas recursivas sino que la tabla de soluciones se llena iterativamente.

 

Ordenemos los intervalos de izquierda a derecha respecto al inicio de los intervalos (ejercicio: será mejor ordenar respecto al final de los intervalos?), de modo que si p<q entonces intervalos[p].inicio≤ intervalos[q].inicio. Sea maxInter[p] el máximo número de intervalos que podemos elegir si el primero (de izquierda a derecha) es el p-ésimo intervalo. Nota que el valor de maxInter[p] solo depende de los intervalos q>p, es decir, de los intervalos que empiezan después de p. Así que el orden en que debemos llenar la tabla maxInter es de derecha a izquierda, es decir, maxInter[n-1], maxInter[n-2],..., maxInter[1], maxInter[0].

 

int maxInter[MAX_N+1];

//maxInter[p] indicará el máximo número de intervalos que podemos elegir, 

//si el primero en ser elegido (contados de izquierda a derecha) es el p-ésimo

int calcularMaxIntervalos(void)

   {

      sort(intervalos de menor a mayor inicio);

      maxInter[n-1]=1;

      for(int p=n-2; p>=0; p--)

         {

            int q=p+1;//q debe indicar el siguiente intervalo que podemos elegir

            while(q<n && intervalos[q].inicio<intervalos[p].final)

               q++;

            maxInter[p]=1;//al menos podamos elegir el intervalo p

            if(q<n)//ademas de tomar el intervalo p, también podemos elegir el q

               maxInter[p]=MAX(maxInter[p], 1+maxInter[q]);                        

          }

      int best=maxInter[0];//este NO es necesariamente el mejor!!! ejercicio: por que?

      for(int p=1;p<n;p++)

         best=MAX(best, maxInter[p]);

      return best;

   }

 

En cada paso del código anterior, suponemos elegimos que el intervalo p. Ahora, dado que lo elegimos, nuestras opciones se reducen a que el siguiente intervalo en ser elegido no empiece antes de que el intervalo p termine. Pero dado que estamos calculando los resultados óptimos de derecha a izquierda, todos los resultados que necesitamos ya fueron calculados, por lo que solo hay que elegir el mayor de todos haciendo referencia a la tabla en lugar de hacer una llamada recursiva.

 

 

Glotón

            Hay una optimización más que es posible hacer en cierto tipo de problemas. En programación dinámica tuvimos que verificar cuál es la solución óptima para todos los q>p tales que el intervalo q no empieza antes de que termine p, es decir, verificar todas las posibles sub-soluciones y elegir la mejor. Ciertos problemas tienen la propiedad de que no es necesario verificar todas las posibles sub-soluciones para saber cual de ellas es la mejor.

 

Ordenemos ahora los intervalos de menor a mayor final, de modo que si p<q entonces intervalos[p].final≤ intervalos[q].final. Supongamos que de todos los intervalos, el que termina primero es [a_i,b_i]. Imagínate ahora que el máximo número de intervalos que puedes elegir es K. De esos K intervalos, sea [a_j,b_j] el que termina primero, entonces el máximo número de intervalos que podemos elegir de modo que no empiecen antes de b_j es K-1, pero, espera! Si esos K-1 intervalos no empiezan antes de b_j entonces tampoco empiezan antes de b_i, porque ya habíamos dicho que b_i ≤ b_j, por lo tanto podemos elegir [a_i,b_i] en lugar de [a_j,b_j], y aún así tenemos K intervalos, es decir, haber elegido desde un principio [a_i,b_i] era “óptimo”. Esta es la parte crucial de la demostración de que elegir siempre el primero en terminar es óptimo, es decir, la propiedad “greedy choice”. Ejercicio: completa la prueba como se vió en el entrenamiento.

 

int calcularMaxIntervalos(void)

   {

      sort(intervalos de menor a mayor final);

      int cuenta=1, ultimoElegido=0, i=1;//elijamos siempre el primero

      while(i<n)

         {

            if(intervalos[ultimoElegido].final<=intervalos[i].inicio)

               {

                  ultimoElegido=i;//aceptar este intervalo.El ultimo elegido es i

                  cuenta++;

               }

            i++;

         }

      return cuenta;

   }