algorithm - used - Planeando una competición
tag de las 20 preguntas (7)
Necesito producir el calendario de un evento deportivo.
Hay 30 equipos. Cada equipo tiene que jugar 8 partidos. Esto significa que no es posible que cada equipo compita nuevamente entre todos los otros equipos, pero debo evitar que dos equipos compitan más de una vez entre sí.
Mi idea fue generar todos los partidos posibles (para 30 equipos: (30*29)/2 = 435 matches ) y seleccionar de esta lista 120 partidos (8 partidos para cada equipo: 8 * 30 / 2 = 120 matches ).
Aquí es donde estoy pasando por un momento difícil: ¿cómo puedo seleccionar estas 120 coincidencias? Intenté algunas soluciones simples (tomar el primer partido de la lista, luego el último, y así sucesivamente) pero no parecen funcionar con 30 equipos. También intenté generar todas las combinaciones posibles de coincidencias y encontrar cuál funciona, pero con 30 equipos, esto es demasiado tiempo de cálculo.
¿Hay un algoritmo existente que podría implementar?
ACTUALIZAR
Lo que necesito producir es un horario simple, sin eliminación. Cada equipo juega 8 partidos, y eso es todo. Al final del día no habrá un ganador.
Cada equipo tendrá su calendario, y este calendario no cambiará si ganan o pierden. La planificación se realiza durante todo el día y es inmutable.
ACTUALIZACIÓN 2
Al principio, no quería poner demasiadas restricciones a mi pregunta, pero parece que sin ninguna restricción (aparte de que cada equipo no compita más de una vez entre sí), es solo una cuestión de elegir al azar 8 partidos para cada uno. equipo.
Así que aquí hay algunos detalles más:
Durante este evento deportivo, hay 6 deportes diferentes (fútbol, balonmano, baloncesto, etc.). Esto significa que hay 6 partidos simultáneos. Se inicia una nueva ronda cada 15 minutos.
Cada equipo tendrá que jugar 8 partidos, y cada deporte al menos una vez.
Estos 6 deportes se llevan a cabo en tres lugares diferentes. Esto significa que durante el día, cada equipo tendrá que moverse de un lugar a otro. Estos movimientos deben reducirse tanto como sea posible.
Un equipo no puede jugar dos partidos seguidos.
¿Seguro que no pudiste conseguir 32 equipos :-)?
Eso haría las cosas más simples: tener una estructura de torneo estándar, pero los perdedores de cada ronda juegan en su propia tabla. Creo que esto maximiza el número de equipos que ganan al menos un partido durante el evento.
Con 30 equipos, podrías hacer que 2 equipos jueguen un ''amistoso'' y tengan un pase en la primera ronda. Pero la organización se vuelve mucho más complicada.
El algoritmo de Broker podría funcionar. Curiosamente, no puedo encontrar una buena descripción en la red, así que intentaré explicar el sistema.
Efectivamente, cada equipo le pedirá a cada equipo una puntuación para un partido y se seleccionará la coincidencia con la puntuación más alta. Esto se repite para cada equipo y partido. El programa resultante se guarda y se calcula una puntuación total. Luego, con diferentes puntos de partida (es decir, podría aleatorizar el orden del equipo), esto se hace nuevamente y, si el puntaje total es mayor, se selecciona este programa. Repita esto hasta que encuentre un cronograma que arroje una puntuación lo suficientemente alta o después de un número predefinido de intentos.
El puntaje total se puede calcular por la distancia recorrida por cada equipo, cuanto menor sea el número, mejor. Obviamente, no eliges partidos que rompan tus reglas (demasiados partidos de tipo similar, los mismos equipos juegan nuevamente entre sí).
La puntuación podría ser algo como esto:
- Si el mismo lugar para el equipo: 100 puntos (es decir, si para ambos = 200).
- Para viajar entre lugares, la puntuación se determina para ambos equipos según la longitud, es decir, A -> B y B -> A 50 puntos (están cerca) A -> C y C -> A 30 puntos (no tan cerca) B - > C y C -> B 0 puntos (los viajes que queremos hacer lo menos posible).
- Si el equipo aún no ha jugado este deporte: 100 puntos.
- Si el equipo ha jugado este deporte una vez: 50 puntos.
Por supuesto, el problema con BA es encontrar buenos valores para diferentes parámetros, por lo que necesitaría dedicar algo de tiempo a encontrarlos.
Estoy agregando una respuesta separada dadas las nuevas restricciones, ya que creo que es más claro que agregar a mi respuesta anterior.
Divida los 30 equipos en 5 grupos, cada uno de 6 equipos: ABCDE
Para el primer período jugarán los grupos A y B.
Luego C&D, E&A, B&C, D&E, para los siguientes 4 segmentos de quince minutos.
Así que al final de 5 * 15 minutos: cada equipo ha jugado dos veces, con al menos un período de descanso entre turnos.
Tiene 20 periodos y todos han jugado 8 veces.
Debería ser fácil permitir que un equipo en el grupo B, por ejemplo, juegue contra 8 de los otros equipos de los otros 17 equipos en los grupos A, B y C.
Por ejemplo, jugar equipos A contra equipos B coincidentes, luego, equipos B contra equipos C coincidentes, luego revertir listas, luego dentro de grupos, luego MOD 2, MOD 3 entre grupos y dentro de grupos.
Eso solo permite minimizar el tiempo de viaje y garantizar que cada equipo juegue en cada tipo de juego. ¿Pero resuelva eso para un grupo y puede aplicar la misma solución a todos los demás?
No conozco una implementación existente, pero aquí hay una posible solución para usted:
Forme tres grupos de 9 equipos y combínelos entre sí para que cada uno juegue una vez contra todos los demás. Cada uno de los 27 equipos ahora juega 8 juegos.
Ahora toma los tres equipos restantes, uno para cada grupo.
Modifica algunos juegos de cada equipo:
1-2 -> 1-10, 2-10
3-4 -> 3-10, 4-10
5-6 -> 5-10, 6-10
7-8 -> 7-10, 8-10
Realmente es bastante simple, solo agrupa el equipo i con i-4 , i-3 , i-2 , i-1 , i+1 , i+2 , i+3 , i+4 . Esto se puede hacer usando el algoritmo a continuación.
import java.util.*;
public class Test {
public static void main(String[] args) {
int TEAMS = 30, MATCHES = 8;
int[] matchCount = new int[TEAMS]; // for a sanity check.
List<Match> matches = new ArrayList<Match>();
for (int team1 = 0; team1 < TEAMS; team1++)
for (int team2 = team1 + 1; team2 <= team1 + MATCHES/2; team2++) {
matches.add(new Match(team1, team2 % TEAMS));
// Just for a sanity check:
matchCount[team1]++;
matchCount[team2 % TEAMS]++;
}
System.out.println(matches);
// Sanity check:
System.out.println(matches.size());
System.out.println(Arrays.toString(matchCount));
}
static class Match {
int team1, team2;
public Match(int team1, int team2) {
this.team1 = team1;
this.team2 = team2;
}
public String toString() {
return team1 + " vs " + team2;
}
}
}
Salida:
[0 vs 1, 0 vs 2, 0 vs 3, 0 vs 4, 1 vs 2, 1 vs 3, 1 vs 4, 1 vs 5, 2 vs 3, 2 vs 4, 2 vs 5, 2 vs 6, 3 vs 4, 3 vs 5, 3 vs 6, 3 vs 7, 4 vs 5, 4 vs 6, 4 vs 7, 4 vs 8, 5 vs 6, 5 vs 7, 5 vs 8, 5 vs 9, 6 vs 7, 6 vs 8, 6 vs 9, 6 vs 10, 7 vs 8, 7 vs 9, 7 vs 10, 7 vs 11, 8 vs 9, 8 vs 10, 8 vs 11, 8 vs 12, 9 vs 10, 9 vs 11, 9 vs 12, 9 vs 13, 10 vs 11, 10 vs 12, 10 vs 13, 10 vs 14, 11 vs 12, 11 vs 13, 11 vs 14, 11 vs 15, 12 vs 13, 12 vs 14, 12 vs 15, 12 vs 16, 13 vs 14, 13 vs 15, 13 vs 16, 13 vs 17, 14 vs 15, 14 vs 16, 14 vs 17, 14 vs 18, 15 vs 16, 15 vs 17, 15 vs 18, 15 vs 19, 16 vs 17, 16 vs 18, 16 vs 19, 16 vs 20, 17 vs 18, 17 vs 19, 17 vs 20, 17 vs 21, 18 vs 19, 18 vs 20, 18 vs 21, 18 vs 22, 19 vs 20, 19 vs 21, 19 vs 22, 19 vs 23, 20 vs 21, 20 vs 22, 20 vs 23, 20 vs 24, 21 vs 22, 21 vs 23, 21 vs 24, 21 vs 25, 22 vs 23, 22 vs 24, 22 vs 25, 22 vs 26, 23 vs 24, 23 vs 25, 23 vs 26, 23 vs 27, 24 vs 25, 24 vs 26, 24 vs 27, 24 vs 28, 25 vs 26, 25 vs 27, 25 vs 28, 25 vs 29, 26 vs 27, 26 vs 28, 26 vs 29, 26 vs 0, 27 vs 28, 27 vs 29, 27 vs 0, 27 vs 1, 28 vs 29, 28 vs 0, 28 vs 1, 28 vs 2, 29 vs 0, 29 vs 1, 29 vs 2, 29 vs 3]
120
[8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8]
Si desea una configuración más aleatoria, simplemente puede asignar un número aleatorio entre 1 y 30 a cada equipo.
Actualizar Para hacer frente a sus restricciones agregadas: Deje que el juego sea de sport i mod 6 .
Si desea un algoritmo simple que produzca un programa en el que los equipos no jueguen entre sí más de una vez, eso no es difícil con los parámetros dados.
Aquí hay un ejemplo para 10 equipos y 5 rondas, la solución se muestra como una matriz donde, si el valor de la programación [i] [j] es cero, los equipos no juegan juntos, y si es un número, entonces se muestra en En qué ronda juegan juntos.
1 2 3 4 5 6 7 8 9 10
1 [0, 5, 0, 4, 0, 3, 0, 2, 0, 1]
2 [5, 0, 4, 0, 3, 0, 2, 0, 1, 0]
3 [0, 4, 0, 3, 0, 2, 0, 1, 0, 5]
4 [4, 0, 3, 0, 2, 0, 1, 0, 5, 0]
5 [0, 3, 0, 2, 0, 1, 0, 5, 0, 4]
6 [3, 0, 2, 0, 1, 0, 5, 0, 4, 0]
7 [0, 2, 0, 1, 0, 5, 0, 4, 0, 3]
8 [2, 0, 1, 0, 5, 0, 4, 0, 3, 0]
9 [0, 1, 0, 5, 0, 4, 0, 3, 0, 2]
10[1, 0, 5, 0, 4, 0, 3, 0, 2, 0]
Así que de esta tabla en primera ronda los equipos (1, 10), (2, 9), (3, 8), (4, 7), (5, 6) juegan, en la segunda ronda los equipos (1, 8 ), (2, 7), (3, 6) ... etc.
Para producir esta tabla, el algoritmo es bastante trivial, aquí hay un código python:
#!/bin/env python
def simpleNRooks(size, rounds, schedule):
'''''' Place n rooks on board so that they don''t hit each other in each round,
nor reuse the spots from previous rounds ''''''
for i in range(size):
for j in range(rounds):
if size-j*2-i-1 < 0:
schedule[i][2*size-j*2-i-1] = j + 1
else:
schedule[i][size-j*2-i-1] = j + 1
# parameters
teams = 10
matches = 5
# prepare the schedule, 0''s designate free space
schedule = [[0 for i in range(teams)] for j in range(teams)]
simpleNRooks(teams, matches, schedule)
print ''Final schedule''
for i in range(teams):
print schedule[i]
Si desea obtener una estructura de datos diferente (por ejemplo, una lista de pares por rondas) puede usar el mismo principio, pero cambiar los bucles.
Usted podría mirar en algunos enfoques de coincidencia ya conocidos:
Por ejemplo, el sistema de ajedrez suizo .
Editar:
Después de leer sus requisitos de nuevo, que todos los equipos deben jugar con cada otro equipo exactamente una vez, y que no es necesario que el ganador se decida. Parece que un solo sistema Round Robin haría lo que quieras. Solo puedes dejar cualquier enfrentamiento extra por encima del 8 que necesitas.