Estoy tratando de crear un planificador de liga deportiva. Tengo problemas para identificar un algoritmo que me ayude a completar cada espacio de manera eficiente.
Los datos de muestra para construir el cronograma serían:
- 10 equipos
- Cada equipo juega entre sí 1 vez (se requieren 45 juegos en total)
- Cada equipo juega no más de 1 vez por día
- En mis pruebas estoy usando 9 días con 5 ranuras por día.
Mesa combinada (contiene 45 combos)
ID
Team1ID
Team2ID
bitAssigned
Tabla de programación (contiene 45 franjas horarias)
ScheduleID
homeTeamID
awayTeamID
GameDate
GameTime
En este momento, mis procedimientos existentes ocupan aproximadamente el 90% de los espacios, dejando el 10% de mis espacios vacíos a un conflicto de programación basado en las reglas anteriores.
Doy vueltas sobre mi tabla de horarios en orden ascendente de fecha / hora.
Mi primer puesto podría ser el sábado a las 8 a.m.
Consulto una lista de equipos que aún no se han programado. Luego hago una serie de posibles combinaciones de esos equipos. Luego uso esa matriz para extraer 1 registro aleatorio de mi tabla de combinaciones de combinaciones que aún no se han programado y ubico a esos equipos en el calendario. Luego configuro esa combinación como se usa.
Repito el ciclo una y otra vez y cada vez que mi lista de equipos disponibles se hace más pequeña y mi matriz como resultado también es más pequeña.
Estoy descubriendo que algunos días van bien, y otros días mis últimos dos últimos equipos restantes ya han jugado en una semana anterior, por lo que no se vuelven a agregar al calendario.
Lo único que no he intentado todavía es "restablecer" los días de conflicto e intentarlos nuevamente para ver si obtengo mejores ubicaciones.
¿Alguien tiene alguna sugerencia?
fuente
Respuestas:
Aquí hay un algoritmo que inventé yo mismo. No sé si ya existe o si es realmente la implementación de round robin:
básicamente comienzas con
y siempre mantenga el 1 en la misma posición y gire el resto.
De esa manera siempre obtendrás un calendario de partidos únicos. Esto es extremadamente fácil de implementar y se escala con cualquier número de oponentes, incluso o de manera desigual. Si tienes un número desigual de oponentes, simplemente no coloques a un equipo en la posición 1 y ellos tienen una ronda libre.
fuente
Creo que lo estás haciendo al revés. No comience con la tabla de programación, comience con una tabla / matriz / cualquiera de las combinaciones de juegos (los 45 juegos). A partir de ahí, es un proceso simple asignar los juegos a un día, basado en un equipo que solo juega una vez al día. Y dado que los enfrentamientos solo ocurren una vez (el Equipo A solo juega contra el Equipo B una vez), la programación es fácil porque solo debes asegurarte de que el enfrentamiento no haya sucedido (las entradas son "únicas" de esa manera).
fuente
Genere el horario de 10 equipos de un solo round robin a continuación. Me llevó unos 3 minutos.
Información del horario:
10 equipos: 1 round robin (solo se muestran las primeras 6 semanas)
Fecha de inicio de la temporada 6/1/15 - fecha de finalización 3/5/15
2 juegos cada martes, 3 juegos cada jueves, 5 juegos cada semana sin fechas de omisión
Utilizamos una computadora de marco principal Honeywell obsoleta y poco menos de 3 años para armar todo esto. Una vez que nuestro software de programación fue depurado, la computadora de marco principal tardó muchas horas buscando millones de permutaciones y combinaciones para calcular y crear los patrones equilibrados para 4 a 22 equipos que estábamos buscando.
No existe un algoritmo que resuelva los problemas generales de programación asociados con los cientos o miles de diferentes tipos de ligas, deportes y situaciones potenciales. Lo que hicimos para resolver este problema fue adoptar un enfoque diferente para calcular los horarios. Comienza con las matemáticas muy complejas para determinar los emparejamientos adecuados del equipo de round robin (emparejamientos), pero eso fue solo el comienzo. Se necesitan otras piezas para crear un programa equilibrado útil que se pueda publicar y distribuir. Los jugadores, entrenadores, padres, etc., todos necesitan saber no solo con quién juegan ; pero donde están jugando ; a qué hora están jugando ; si están en casa o visitantes ; y para muchas ligas, un número de juego .
Espero que esto les ayude a usted y a otros a comprender lo que nos llevó 3 años descubrir.
fuente