Diferencia entre revisiones de «El problema de la organización del calendario de un campeonato con Divide y Vencerás»
Contenido eliminado Contenido añadido
m m |
|||
Línea 1:
{{
== 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<sup>2</sup>
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<sup>k</sup> podemos subdividir el problema en dos: que vayan desde '''1''' a '''2<sup>k-1</sup>''' participantes, y el otro desde ''2<sup>k-1</sup>+1''' a '''2<sup>n</sup>''' 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<sup>k-1</sup>+1''',...,'''2<sup>n</sup>'''.
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.
{| width="36%" border="1"
|-----
| <p><font color="#8000FF">'''Caso básico:'''</font></p>
{| width="9%" border="1"
|-----
| width="52%" |
| width="48%" | '''<font color="#00FF00">1</font>'''
|-----
| <font color="#00FF00">'''1'''</font>
| '''2'''
|-----
| <font color="#00FF00">'''2'''</font>
| '''1'''
|}
<p><font color="#8000FF">'''Caso recursivo:'''</font></p>
{| width="40%" border="1"
|-----
|
| '''<font color="#00FF00">1</font>'''
| '''<font color="#00FF00">2</font>'''
| '''<font color="#00FF00">3</font>'''
|-----
| '''<font color="#00FF00">1</font>'''
| '''2''' || '''3''' || '''4'''
|-----
| '''<font color="#00FF00">2</font>'''
| '''1''' || '''4''' || '''3'''
|-----
| '''<font color="#00FF00">3</font>'''
| '''4''' || '''1''' || '''2'''
|-----
| '''<font color="#00FF00">4</font>'''
| '''3''' || '''2''' || '''1'''
|}
|}
<p> </p>
'''El resultado del calendario del campeonato es de la forma:'''
{| width="40%" border="1"
|-----
| <font size="3"> </font>
| <font color="#00FF00" size="3">'''1'''</font>
| <font color="#00FF00" size="3">'''2'''</font>
| <font color="#00FF00" size="3">'''3'''</font>
| <font color="#00FF00" size="3">'''4'''</font>
| <font color="#00FF00" size="3">'''5'''</font>
| <font color="#00FF00" size="3">'''6'''</font>
| <font color="#00FF00" size="3">'''7'''</font>
|-----
| '''<font color="#00FF40" size="3">1</font>'''
| '''<font color="#0000FF" size="3">2</font>'''
| '''<font color="#0000FF" size="3">3</font>'''
| '''<font color="#0000FF" size="3">4</font>'''
| '''<font color="#000000" size="3">5</font>'''
| <font color="#FF0080" size="3">'''6'''</font>
| <font color="#FF0080" size="3">'''7'''</font>
| <font color="#FF0080" size="3">'''8'''</font>
|-----
| '''<font color="#00FF40" size="3">2</font>'''
| '''<font color="#0000FF" size="3">1</font>'''
| '''<font color="#0000FF" size="3">4</font>'''
| '''<font color="#0000FF" size="3">3</font>'''
| '''<font color="#000000" size="3">8</font>'''
| <font color="#FF0080" size="3">'''5'''</font>
| <font color="#FF0080" size="3">'''6'''</font>
| <font color="#FF0080" size="3">'''7'''</font>
|-----
| '''<font color="#00FF40" size="3">3</font>'''
| '''<font color="#0000FF" size="3">4</font>'''
| '''<font color="#0000FF" size="3">1</font>'''
| '''<font color="#0000FF" size="3">2</font>'''
| '''<font color="#000000" size="3">7</font>'''
| <font color="#FF0080" size="3">'''8'''</font>
| <font color="#FF0080" size="3">'''5'''</font>
| <font color="#FF0080" size="3">'''6'''</font>
|-----
| '''<font color="#00FF40" size="3">4</font>'''
| '''<font color="#0000FF" size="3">3</font>'''
| '''<font color="#0000FF" size="3">2</font>'''
| '''<font color="#0000FF" size="3">1</font>'''
| '''<font color="#000000" size="3">6</font>'''
| <font color="#FF0080" size="3">'''7'''</font>
| <font color="#FF0080" size="3">'''8'''</font>
| <font color="#FF0080" size="3">'''5'''</font>
|-----
| '''<font color="#00FF40" size="3">5</font>'''
| '''<font color="#FF0080" size="3">6</font>'''
| '''<font color="#FF0080" size="3">7</font>'''
| '''<font color="#FF0080" size="3">8</font>'''
| <font color="#000000" size="3">'''1'''</font>
| '''<font color="#0000FF" size="3">2</font>'''
| '''<font color="#0000FF" size="3">3</font>'''
| '''<font color="#0000FF" size="3">4</font>'''
|-----
| '''<font color="#00FF40" size="3">6</font>'''
| '''<font color="#FF0080" size="3">5</font>'''
| '''<font color="#FF0080" size="3">8</font>'''
| '''<font color="#FF0080" size="3">7</font>'''
| <font color="#000000" size="3">'''4'''</font>
| '''<font color="#0000FF" size="3">1</font>'''
| '''<font color="#0000FF" size="3">2</font>'''
| '''<font color="#0000FF" size="3">3</font>'''
|-----
| '''<font color="#00FF40" size="3">7</font>'''
| '''<font color="#FF0080" size="3">8</font>'''
| '''<font color="#FF0080" size="3">5</font>'''
| '''<font color="#FF0080" size="3">6</font>'''
| <font color="#000000" size="3">'''3'''</font>
| '''<font color="#0000FF" size="3">4</font>'''
| '''<font color="#0000FF" size="3">1</font>'''
| '''<font color="#0000FF" size="3">2</font>'''
|-----
| '''<font color="#00FF40" size="3">8</font>'''
| '''<font color="#FF0080" size="3">7</font>'''
| '''<font color="#FF0080" size="3">6</font>'''
| '''<font color="#FF0080" size="3">5</font>'''
| <font color="#000000" size="3">'''2'''</font>
| '''<font color="#0000FF" size="3">3</font>'''
| '''<font color="#0000FF" size="3">4</font>'''
| '''<font color="#0000FF" size="3">1</font>'''
|}
== Seudo-código ==
La implementación se realiza con una tabla de la forma:
'''tabla[participante, dia]=contrincante'''
<code>
'''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 2<sup>k-1</sup>*/
formarTabla(t,primero,medio);
/*segunda subsolución: participantes de 2<sup>k-1</sup>+1 a 2<sup>k</sup>*/
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'''
</code>
<code>
'''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'''
</code>
'''Procedimiento principal que realiza la inicialización adecuada:'''
<code>
'''Procedimiento''' Calendario (ent/sal t: tabla)
'''begin'''
/*llamada inicial*/
formarTabla(t,1,n);
'''end'''
</code>
| |||