Todo se puede aprender
...si se quiere.

Algoritmo para Crear un Fixture

26 de mayo de 2014 | 21:08


Algoritmo para generar un Calendario Deportivo.



El problema que se resolverá es el siguiente:
Es necesario diseñar un fixture para organizar los partidos de un campeonato de fútbol. Las restricciones que tiene el problema son las siguientes:

  • Existen 4 equipos que deben jugar.
  • Deben jugar todos contra todos.
  • Hay dos partidos por cada par de equipos posibles (intercambiando los roles de local y visita).
  • Un equipo sólo puede jugar un partido por fecha.
  • Dos equipos no pueden jugar entre sí en 2 fechas consecutivas, es decir, si Colo Colo juega con Universidad de Chile en la fecha 5, en la fecha 6 estos dos equipos no pueden enfrentarse nuevamente.
  • Un equipo no puede jugar más de 2 veces consecutivas de local o de visita, es decir, si Cobreloa jugó sus últimos dos partidos de local, en el próximo partido debe jugar de visita.

Deducciones:

  • Cantidad de equipos = a = 4
  • Cantidad de partidos = b
  • Cantidad partidos simultáneos = c
  • Cantidad de fechas =  d


La cantidad de partidos a jugar se puede calcular mediante la variación entre la cantidad de equipos que participarán en el campeonato y la cantidad de equipos que participan por partido, esto es la variación entre 4 y 2.

La cantidad de partidos simultáneos por fecha corresponde a la mitad de la cantidad de equipos que participarán en el campeonato.

Finalmente, la cantidad de fechas corresponde al cuociente entre la cantidad de partidos y la cantidad de partidos simultáneos.

A continuación se describe un algoritmo en pseudo-código que permite determinar de manera aproximada un Calendario Deportivo.

Arreglo[][] algoritmoFixture(Arreglo[4] equipos){
         CONSTANTE entero numeroFechas = 6;
         CONSTANTE entero numeroEquipos = 4;
         CONSTANTE entero numeroPartidos = 12;
         Arreglo[numeroPartidos][3] fixture;
         int local,visita;
         int programandoPartido = 1;
         int programandoFecha = 1;
         Arreglo[numeroEquipos] disponibles;
         Arreglo[numeroEquipos][ numeroEquipos] matriz ;
         Arreglo[numeroEquipos][2] registroHap;
         Arreglo[numeroEquipos] ultimaFecha;
         boolean iguales, disponibilidad, programado, rival, hapLocal, hapVisita,  hap ;
         llenarMatriz(matriz);
         llenarHap(registroHap);
         while(programandoFecha<=numeroFechas){
            reiniciarDisponibles(disponibles);
            Para local=0 hasta numeroEquipos-1 {
               Para visita=0 hasta numeroEquipos-1{
                  iguales = (local != visita);
                  programado = matriz[local][visita]==0;
                  disponibilidad = disponibles[local]==0 && disponibles[visita]==0;
                  rival = visita != ultimaFecha[local];
                  Si ( registroHap[local][0]!=0 || (registroHap[local][0]==0 &&                                                                                                
                         registroHap[local][1]>0) )
                                        hapLocal = true;
                         Sino
                                        hapLocal = false;
                        Si ( registroHap[visita][0]!=1 || (registroHap[visita][0]==1 &&
                               registroHap[visita][1]>0) )
                                        hapVisita = true;
                         Sino
                                        hapVisita = false;
                                        hap = hapLocal && hapVisita;
                  Si (iguales && disponibilidad && programado && rival && hap){
                     matriz[local][visita]=programandoPartido;
                    fixture[programandoPartido-1][0] = tring.valueOf(programandoFecha);
                     fixture[programandoPartido-1][1] = equipos[local];
                     fixture[programandoPartido-1][2] = equipos[visita];
                     disponibles[local]=1;
                     disponibles[visita]=1;
                     ultimaFecha[local] = visita;
                     ultimaFecha[visita] = local;
                     Si (registroHap[local][0]==0)
                        registroHap[local][1]--;
                     Sino{
                        registroHap[local][0] = 0;
                        registroHap[local][1] = 1;
                     }
                     Si (registroHap[visita][0]==1)
                        registroHap[visita][1]--;
                     Sino{
                        registroHap[visita][0] = 1;
                        registroHap[visita][1] = 1;
                     }
                     programandoPartido++;
                  }
               }
            }
            programandoFecha++;                            
         }
         retornar(fixture);
      }

Un ejemplo del algoritmo

Consideremos un calendario para 4 equipos.
Se crea una matriz de 4x4 donde cada posición representa un partido posible y donde cada fila y columna representa un equipo (Como se muestra en la figura 4.1).


La idea es ir recorriendo esta matriz posición por posición y verificar las restricciones del problema, si las restricciones se cumplen en una posición determinada se ingresa el número del partido que se está programando. (Ya sabemos que serán 12 partidos)
Para ayudar a verificar las restricciones se hará uso de varios arreglos y matrices

Arreglo “disponibles”

Este arreglo indica si un equipo está disponible en un determinado momento, recordemos que un equipo sólo puede jugar un partido por fecha, por lo que si se programa un partido, ambos equipos deben quedar no disponibles mientras se siga programando esa fecha. (0=disponible, 1=no disponible). En la figura 4.2 se puede ver que las posiciones 0 y 1 tienen valor 0 y las posiciones 2 y 3 tienen valor 1, lo que quiere decir que Colo-Colo y U. de Chile están disponibles para jugar y la U. Católica con Cobreloa ya se les programó un partido.
Figura 4.2: Arreglo “disponibles”

Arreglo “ultimaFecha”

Este arreglo indicará para cada equipo cuál fue su rival en la fecha pasada, esto nos servirá para controlar que dos equipos no jueguen entre sí en dos fechas consecutivas. En figura 4.3 podemos ver que la posición 0 tiene valor 3, esto quiere decir que Colo Colo jugó en la última fecha con el equipo “3”, que es Cobreloa.

Matriz “registroHap”

El HAP de un equipo es la secuencia de partidos que juega de local y de visita. Por ejemplo el HAP LLVV indica que se jugaron 2 partidos de local y luego dos partidos de visita.
En nuestro problema tenemos la restricción de que un equipo no puede jugar más de dos partidos seguidos de local o de visita, por ejemplo el HAP LVLVLLL sería inválido, ya que se jugaron 3 partidos consecutivos de local.
Para controlar esta restricción tenemos una matriz que nos indica en la primera columna de que jugó un equipo en la fecha pasada (local o visita) y en la segunda columna cuántos partidos puede seguir jugando en esa condición.
En la figura 4.4 podemos ver que la posición 0 tiene los valores 0 y 0, lo que quiere decir que Colo Colo jugó su último partido de local y que ya no puede seguir jugando en esa condición. En cambio, la posición 1 que es U. de Chile tiene los valores 1 y 1 lo que quiere decir que su último partido lo jugó de visita y que todavía puede jugar un partido más en esa condición.
(0=local , 1=visita).

Compartir