Algoritmia/Divide y vencerás/Organización del calendario de un campeonato

El problema de la organización del calendario de un campeonato con Divide y Vencerás.

Objetivo

Se organiza un torneo con n participantes. Cada participante tiene que competir exactamente una vez con todos los posibles oponentes. Además, cada participante tiene que jugar exactamente un partido cada día, con la posible excepción de un solo día en el cual pueda sentarse en el banquillo.

Descripción

Si n es una potencia de 2, dar un algoritmo para construir un horario que permita que el torneo concluya en n-1 días.

Esquema

La estrategia Divide y Vencerás consiste en descomponer un problema en subproblemas más simples del mismo tipo, resolverlos de forma independiente y una vez obtenidas las soluciones parciales combinarlas para obtener la solución del problema original.

Suposiciones

Por concreción, y sin perdida de generalidad, puede suponerse que las competiciones se celebran en días sucesivos y que cada participante compite una vez por día. El número de participantes es potencia de dos, que nos simplificará el problema. Por lo tanto n = 2k participantes, con k entero positivo.

Idea: Cada participante tiene un número asignado de 1 a n. La técnica que seguiremos nosotros es la de DIVIDE Y VENCERÁS.

FUERZA BRUTA => n! Pues tendríamos n! permutaciones que equivalen a posibles formas de rellenar la tabla.

DIVIDE Y VENCERÁS => n² En la técnica divide y vencerás descomponemos el problema en un conjunto de subproblemas más pequeños. En nuestro caso, el coste cuadrático se debe a que, al combinar las soluciones para obtener la solución para el problema original se realizan dos bucles anidados completando el resto de la tabla con los mismos valores existentes en la otra mitad. MUCHO MÁS EFICIENTE QUE LA FUERZA BRUTA

La solución del problema puede representarse en una tabla de dimensión n*(n-1). El elemento (i, j)–esimo de la tabla, 1<= i<=n, 1<=j<n, contiene el número del participante contra el que el participante i-esimo compite el día j-esimo.

Ejemplo

Caso básico

Se da cuando solo tenemos dos participantes. La solución es inmediata puesto que competirán entre ambos.

Caso recursivo

Se da cuando tenemos más de dos participantes. Partiendo del problema de tamaño 2^k podemos subdividir el problema en dos: que vayan desde 1' a 2^k-1 participantes, y el otro desde 2^k-1+1 a 2ⁿ participantes.

La unión de los dos subresultados no da la solución final. Después de conseguirlas individualmente tendremos que combinarlas: Para ello habrá que cruzarlas puesto que faltan las competiciones de los participantes de la primera subsolución con los de la segunda. Se trata de que los participantes de la primera parte jueguen con los de la segunda y viceversa. Para formar el subcalendario del primer participante basta con que compita en días sucesivos con los participantes de numeración superior en orden creciente, es decir, sucesivamente con los participantes 2^k-1+1,...,2ⁿ.

El siguiente participante toma esta secuencia y realiza una permutación de la misma rotando dicha secuencia a la derecha. Este proceso se repite para el resto de los participantes de numeración inferior.

Caso básico:   1 1 2 2 1 Caso recursivo:   1 2 3 1 2 3 4 2 1 4 3 3 4 1 2 4 3 2 1

 

El resultado del calendario del campeonato es de la forma:

	1	2	3	4	5	6	7
1	2	3	4	5	6	7	8
2	1	4	3	8	5	6	7
3	4	1	2	7	8	5	6
4	3	2	1	6	7	8	5
5	6	7	8	1	2	3	4
6	5	8	7	4	1	2	3
7	8	5	6	3	4	1	2
8	7	6	5	2	3	4	1

Pseudo-código

La implementación se realiza con una tabla de la forma: tabla[participante, dia]=contrincante

Procedimiento formarTabla(ent/sal t: tabla; primero, ultimo:1..n)

var
medio: 1..n;
begin
  si ultimo - primero == 1  entonces  
      /*caso base: compiten entre ambos (el mismo día)*/
      t[primero,1]=ultimo;
      t[ultimo,1]=primero;
  sino
      medio = (primero+ultimo) div 2;
      /*primera subsolución: participantes de 1 a 2k-1*/
                                                
      formarTabla(t,primero,medio);
      /*segunda subsolución: participantes de 2k-1+1 a 2k*/  
                                  
      formarTabla(t,medio+1,ultimo);
      /*completa la tabla de los participantes de la primera subsolución con los de la segunda*/
      completarTabla(t, primero, medio, medio-primero+1, ultimo-primero, medio+1);
      /*completa la tabla de los participantes de la segunda subsolución con los de la primera*/
      completarTabla(t, medio+1, ultimo, medio-primero+1, ultimo-primero, primero);
   fsi
end

Procedimiento CompletarTabla(ent/sal t: tabla; eqInf, eqSup, díaInf, díaSup,eqInicial: 1..n)

begin
  para j = díaInf hasta díaSup hacer
      t[eqInf,j] = eqInicial + j – diaInf;
  fpara;
  para i = eqInf + 1 hasta eqSup hacer
      /*Intercambio de contrincante*/
      t[i,díaInf] = t[i-1, díaSup]; {el último contrincante de i-1 es ahora el primer contrincante de i}
      para j = díaInf + 1 hasta díaSup hacer
         /*rotación de los contrincantes*/
         t[i,j] = t[i-1,j-1]; {el contrincante de ayer de i-1, es el contrincante de hoy para i}
      fpara;
  fpara;
end

Procedimiento principal que realiza la inicialización adecuada:

Procedimiento Calendario (ent/sal t: tabla)

begin
     /*llamada inicial*/
     formarTabla(t,1,n);
end