J'essaie de créer un calendrier de ligue sportive. J'ai du mal à identifier un algorithme pour m'aider à remplir efficacement chaque emplacement.
Des exemples de données pour construire le calendrier seraient:
- 10 équipes
- Chaque équipe se joue 1 fois (45 matchs au total requis)
- Chaque équipe ne joue pas plus d'une fois par jour
- Dans mes tests, j'utilise 9 jours avec 5 emplacements par jour.
Table combinée (contient 45 combos)
ID
Team1ID
Team2ID
bitAssigned
Tableau des horaires (contient 45 plages horaires)
scheduleID
homeTeamID
awayTeamID
GameDate
GameTime
À l'heure actuelle, mes procédures existantes remplissent environ 90% des emplacements, laissant 10% de mes emplacements vides à un conflit d'horaire basé sur les règles ci-dessus.
Je passe en revue ma table de programme dans l'ordre croissant de date / heure.
Ma première place pourrait être samedi à 8h.
Je recherche une liste d'équipes qui n'ont pas encore été programmées. Je fais ensuite un éventail de combinaisons possibles de ces équipes. J'utilise ensuite ce tableau pour extraire 1 enregistrement aléatoire de ma table de combinaisons de combinaisons qui n'ont pas encore été planifiées et je place ces équipes sur le calendrier. J'ai ensuite défini cette combinaison comme utilisée.
Je répète la boucle encore et encore et à chaque fois que ma liste d'équipes disponibles se réduit et que mon tableau est également plus petit.
Je constate que certains jours se passent bien, et d'autres jours, mes 2 dernières équipes restantes ont déjà joué la semaine précédente, donc elles ne sont pas ajoutées au calendrier.
La seule chose que je n'ai pas encore essayée est de "réinitialiser" les jours de conflit et de les réessayer pour voir si j'obtiens de meilleurs placements.
Est-ce que quelqu'un a des suggestions?
la source
Réponses:
Voici un algorithme que j'ai inventé moi-même. Je ne sais pas s'il existe déjà ou s'il s'agit en fait de l'implémentation du tournoi à la ronde:
vous commencez avec
et gardez toujours le 1 dans la même position et tournez le reste.
De cette façon, vous obtiendrez toujours un calendrier de matchs uniques. Ceci est extrêmement facile à mettre en œuvre et s'adapte à n'importe quel nombre d'adversaires, même ou irrégulier. Si vous avez un nombre irrégulier d'adversaires, ne placez pas une équipe en 1 position et ils ont un tour gratuit.
la source
Je pense que vous le faites à l'envers. Ne commencez pas avec le tableau de programmation, commencez par un tableau / tableau / quelle que soit toutes les combinaisons de jeux (les 45 jeux). À partir de là, c'est un processus simple d'affecter les jeux à une journée, basé sur une équipe qui ne joue qu'une fois par jour. Et comme les matchs ne se produisent qu'une seule fois (l'équipe A ne joue qu'une seule fois contre l'équipe B), la planification est facile car il vous suffit de vous assurer que le match n'a pas déjà eu lieu (les entrées sont "uniques" de cette façon).
la source
J'ai généré le calendrier du tournoi à la ronde à 10 équipes ci-dessous. Cela m'a pris environ 3 minutes.
Informations sur les horaires:
10 équipes - 1 tournoi à la ronde (seules les 6 premières semaines sont affichées)
Date de début de saison 1/6/15 - date de fin 3/5/15
2 matchs chaque mardi, 3 matchs chaque jeudi, 5 matchs chaque semaine sans dates de saut
Nous avons utilisé un ordinateur principal Honeywell obsolète et un peu moins de 3 ans pour assembler le tout. Une fois notre logiciel de planification débogué, il a fallu plusieurs heures à l'ordinateur principal pour rechercher des millions de permutations et de combinaisons afin de calculer et de créer les modèles équilibrés pour 4 à 22 équipes que nous recherchions.
Il n'y a pas d'algorithme qui résout les problèmes de planification globale associés aux centaines ou milliers de différents types de ligues, de sports et de situations potentielles. Ce que nous avons fait pour résoudre ce problème était d'adopter une approche différente pour calculer les horaires. Cela commence par des calculs très complexes pour déterminer les bons couples d'équipes de tournoi à la ronde (matchs), mais ce n'était que le début. D'autres pièces sont nécessaires pour créer un calendrier équilibré utile qui peut être publié et distribué. Les joueurs, entraîneurs, parents, etc., ont tous besoin de savoir non seulement à qui ils jouent ; mais où ils jouent ; à quelle heure ils jouent ; s'ils sont à la maison ou en visite ; et pour de nombreuses ligues, un numéro de match .
J'espère que cela vous aide, vous et d'autres, à comprendre ce qui nous a pris 3 ans pour comprendre.
la source