Estou tentando criar um agendador de liga esportiva. Estou tendo problemas para identificar um algoritmo para me ajudar a preencher com eficiência cada slot.
Os dados de amostra para criar a programação seriam:
- 10 equipes
- Cada time joga um ao outro uma vez (são necessários 45 jogos no total)
- Cada equipe joga no máximo 1 vez por dia
- Nos meus testes, estou usando 9 dias com 5 slots por dia.
Tabela Combo (contém 45 combos)
ID
Team1ID
Team2ID
bitAssigned
Tabela de agendamento (contém 45 horários)
scheduleID
homeTeamID
awayTeamID
GameDate
GameTime
No momento, meus procedimentos existentes preenchem cerca de 90% dos slots, deixando 10% dos slots vazios para um conflito de agendamento com base nas regras acima.
Percorro minha tabela de agendamento em ordem crescente de data / hora.
Meu primeiro horário poderia ser no sábado às 8h.
Consulto uma lista de equipes que ainda não foram agendadas. Em seguida, faço uma série de combinações possíveis dessas equipes. Em seguida, uso essa matriz para extrair 1 registro aleatório da minha tabela de combinações de combinações que ainda não foram agendadas e coloco essas equipes na programação. Em seguida, defino essa combinação como usada.
Repito o ciclo repetidamente e cada vez que minha lista de equipes disponíveis fica menor e minha matriz, como resultado, também é menor.
Estou descobrindo que alguns dias correm bem e, em outros, meus últimos 2 times restantes já jogaram na semana anterior, para que não sejam adicionados à programação novamente.
A única coisa que ainda não tentei é "redefinir" os dias de conflito e experimentá-los novamente para ver se consigo melhores posicionamentos.
Alguém tem alguma sugestão?
fonte
Respostas:
Aqui está um algoritmo que eu me inventei. Não sei se ele já existe ou é realmente a implementação de rodízio:
basicamente você começa com
e sempre mantenha o 1 na mesma posição e gire o resto.
Dessa forma, você sempre terá uma programação de correspondências únicas. Isso é extremamente fácil de implementar e dimensiona com qualquer número de oponentes, pares ou desiguais. Se você tem um número desigual de oponentes, não coloque um time na posição 1 e eles terão uma rodada grátis.
fonte
Eu acho que você está fazendo isso ao contrário. Não comece com a tabela de agendamento, comece com uma tabela / matriz / qualquer que seja a combinação de jogos (os 45 jogos). A partir daí, é um processo simples atribuir os jogos a um dia, com base em uma equipe que joga apenas uma vez por dia. E como os confrontos acontecem apenas uma vez (o time A joga o time B apenas uma vez), o agendamento é fácil porque você só precisa se certificar de que o confronto ainda não aconteceu (as entradas são "únicas" dessa maneira).
fonte
Gerei o cronograma de 10 rodadas de equipe única abaixo. Demorei cerca de 3 minutos.
Informações da programação:
10 equipes - 1 round robin (apenas as 6 primeiras semanas são exibidas)
Data de início da temporada 1/6/15 - data final 3/5/15
2 jogos a cada terça-feira, 3 jogos a cada quinta-feira, 5 jogos a cada semana sem pular datas
Usamos um computador com estrutura principal desatualizado da Honeywell e pouco menos de três anos para montar tudo isso. Depois que nosso software de agendamento foi depurado, o computador de quadro principal levou muitas horas pesquisando milhões de permutações e combinações para calcular e criar os padrões balanceados para 4 a 22 equipes que estávamos procurando.
Não existe um algoritmo que resolva os problemas gerais de programação associados a centenas ou milhares de tipos diferentes de ligas, esportes e situações potenciais. O que fizemos para resolver esse problema foi adotar uma abordagem diferente para calcular os cronogramas. Começa com a matemática muito complexa para determinar os pares adequados de equipes de rodízio (match-ups), mas isso foi apenas o começo. Outras peças são necessárias para criar uma programação equilibrada útil que possa ser publicada e distribuída. Jogadores, treinadores, pais, etc., todos precisam saber não apenas quem eles estão jogando ; mas onde eles estão jogando ; a que horas eles estão jogando ; se eles estão em casa ou visitante ; e para muitas ligas, um número de jogo .
Espero que isso ajude você e outras pessoas a entender o que levou três anos para descobrir.
fonte