Ir al contenido

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

De Wikilibros, la colección de libros de texto de contenido libre.

Objetivo

[editar]

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

[editar]

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

[editar]

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

[editar]

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 => n2 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

[editar]

Caso básico

[editar]

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

Caso recursivo

[editar]

Se da cuando tenemos más de dos participantes. Partiendo del problema de tamaño 2k podemos subdividir el problema en dos: que vayan desde 1' a 2k-1 participantes, y el otro desde 2k-1+1 a 2n 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 2k-1+1,...,2n.

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

Seudo-código

[editar]

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, ultimo-1, medio+1); 
      /*completa la tabla de los participantes de la segunda subsolución con los de la primera*/ 
      completarTabla(t, medio+1, ultimo, medio, ultimo-1, 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] = eqInic + 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