Existe um algoritmo conhecido para agendar partidas de torneios?

10

Imaginando se já existe algum algoritmo de programação de torneios que eu poderia usar ou até adaptar um pouco.

Aqui estão os meus requisitos:

  • Um número variável de oponentes pertencentes a um número variável de equipes / clubes deve ser emparelhado com um oponente
  • Dois oponentes não podem ser do mesmo clube
  • Se houver um número ímpar de jogadores, 1 deles é selecionado aleatoriamente para obter um adeus

Qualquer algoritmo relacionado a esse tipo de conjunto de requisitos seria apreciado.

Edição: Eu só preciso executar isso no máximo uma vez, criando confrontos para a primeira 'rodada' do torneio.

algorithms barfoon
fonte
Você pode procurar a correspondência máxima .
precisa

Respostas:

1

Do meu breve período na Wikipedia, há vinte segundos, parece que você precisará decidir primeiro uma estratégia de eliminação. Veja Wikipedia:

  1. Sistema Suíço
  2. Torneio-eliminatório-único
  3. Eliminação dupla_tournament

O artigo de eliminatória simples descrita semear técnicas (o algoritmo que você está procurando) muito genericamente e parecia útil, embora não seja muito um algoritmo.

Chris Pfohl
fonte
Prefiro o suíço, que classifica o meio ao contrário da eliminação dupla / única e encontra os melhores jogadores do N no mesmo número de rodadas que um torneio de eliminação N.
Mooing Duck
1

Com isso, parece que um algoritmo de correspondência inicial é bastante simples:

While two or more clubs have at least one member not paired  
    select the two clubs with the most unpaired members
    select a random unpaired member from each club
    pair those members

Se uma pessoa for deixada, será uma pessoa aleatória, com uma exceção. Se um clube tiver mais membros do que todos os jogadores adversários juntos, as sobras serão sempre desse clube. Realisticamente, essa é uma situação super-rara, e escolher uma compra de qualquer outro clube deixaria ainda mais pessoas sobrando.

Mooing Duck
fonte