Calendrier des matchs de tennis

Question

Il y a un nombre limité de joueurs et un nombre limité de courts de tennis. À chaque tour, il peut y avoir au plus que le nombre de matches qu'il y a des tribunaux. Personne ne joue 2 tours sans une pause. Tout le monde joue un match contre tous les autres. Produire de l'annexe qui prend aussi peu de tours que possible. (En raison de la règle qu'il doit y avoir une pause entre les tours pour tout le monde, il y a peut être un tour sans les matchs.) La sortie pour 5 joueurs et 2 les tribunaux pourraient être:

 |  1   2   3   4   5
-|------------------- 
2|  1   - 
3|  5   3   - 
4|  7   9   1   - 
5|  3   7   9   5   -

Dans cette sortie, les colonnes et les lignes sont les joueurs eux-mêmes chiffres, et les nombres à l'intérieur de la matrice sont les chiffres ronds, ces deux joueurs s'affrontent.

Le problème est de trouver un algorithme qui peut le faire pour les grandes instances dans un temps faisable. On nous a demandé de le faire dans le Prologue, mais (pseudo-) code dans n'importe quelle langue serait utile.

Mon premier essai a été un algorithme glouton, mais qui donne des résultats avec trop de tours. Alors j'ai proposé un approfondissement itératif depth-first search, qui un de mes amis en œuvre, mais qui a quand même pris beaucoup trop de temps sur les instances aussi petit que 7 joueurs.

(Ce est à partir d'un vieux de questions d'examen. Nul j'ai parlé a une solution.)

Answer 1

Exemple de solution Prolog utilisant SWI-Prolog:

 :- use_module(library(clpfd)).

tennis(N, Courts, Rows) :-
        length(Rows, N),
        maplist(length_(N), Rows),
        transpose(Rows, Rows),
        Rows = [[_|First]|_],
        chain(First, #<),
        length(_, MaxRounds),
        numlist(1, MaxRounds, Rounds),
        pairs_keys_values(Pairs, Rounds, Counts),
        Counts ins 0..Courts,
        triangle(Rows, 0, Ts, Ds),
        append(Ts, TVs),
        global_cardinality(TVs, Pairs),
        maplist(breaks, Ds),
        labeling([ff], TVs).

triangle([], _, [], []).
triangle([R|Rs], N, [T|Ts], [D|Ds]) :-
        length(Prefix, N),
        append(Prefix, [-|T], R),
        append(Prefix, T, D),
        N1 #= N + 1,
        triangle(Rs, N1, Ts, Ds).

breaks([]).
breaks([P|Ps]) :- maplist(breaks_(P), Ps), breaks(Ps).

breaks_(P0, P) :- abs(P0-P) #> 1.

length_(L, Ls) :- length(Ls, L).
 

5 joueurs sur 2 terrains:

 ?- time(tennis(5, 2, Rows)), maplist(writeln, Rows).
% 827,838 inferences, 0.257 CPU in 0.270 seconds (95% CPU, 3223518 Lips)
[-,1,3,5,7]
[1,-,5,7,9]
[3,5,-,9,1]
[5,7,9,-,3]
[7,9,1,3,-]
 

6 joueurs sur 2 terrains:

 ?- time(tennis(6, 2, Rows)), maplist(writeln, Rows).
% 5,605,107 inferences, 1.775 CPU in 2.137 seconds (83% CPU, 3156941 Lips)
[-,1,3,5,7,10]
[1,-,6,9,11,3]
[3,6,-,11,9,1]
[5,9,11,-,2,7]
[7,11,9,2,-,5]
[10,3,1,7,5,-]
 

7 joueurs sur 5 terrains:

 ?- time(tennis(7, 5, Rows)), maplist(writeln, Rows).
% 105,563,012 inferences, 35.757 CPU in 46.680 seconds (77% CPU, 2952225 Lips)
[-,1,3,5,7,9,11]
[1,-,5,3,11,13,9]
[3,5,-,9,1,7,13]
[5,3,9,-,13,11,7]
[7,11,1,13,-,5,3]
[9,13,7,11,5,-,1]
[11,9,13,7,3,1,-]
 

Answer 2

Ceci est très similaire à l' Voyager Tournoi Problème, qui est sur la planification des équipes de football. Dans le TTP, ils peuvent trouver la solution optimale à seulement 8 équipes. Toute personne qui enfreint un dossier permanent de 10 équipes ou plus, il est beaucoup plus facile de se faire publier dans un journal de recherche.

Il est NP-difficile et l'astuce est d'utiliser les méta-heuristiques, comme la recherche tabou, le recuit simulé, ... au lieu de la force brute ou de branch and bound.

Prendre un coup d'oeil à ma mise en œuvre avec Drools Planner (open source, java). Voici les contraintes, il doit être facile à remplacer qu'avec des contraintes telles que Personne ne joue 2 tours sans une pause.

Answer 3

Chaque joueur doit jouer au moins n - 1 correspond à l'endroit où n est le nombre de joueurs. De sorte que le minimum de tours est 2(n - 1) - 1, puisque chaque joueur reste un match. Le minimum est également lié par (n(n-1))/2 total correspond divisé par le nombre de tribunaux. En utilisant la plus petite de ces deux vous donne la longueur de la solution optimale. Puis c'est une question de venir avec une bonne basse de l'estimation de la formule ((nombre de matchs+repose restant)/courts) et de lancer Une recherche* .

Comme Geoffrey dit, je crois que le problème est NP-Difficile, mais la méta-heuristiques telles que A* est très applicable.

Answer 4

Solution Python:

 import itertools

def subsets(items, count = None):
    if count is None:
        count = len(items)

    for idx in range(count + 1):
        for group in itertools.combinations(items, idx):
            yield frozenset(group)

def to_players(games):
    return [game[0] for game in games] + [game[1] for game in games]

def rounds(games, court_count):
    for round in subsets(games, court_count):
        players = to_players(round)
        if len(set(players)) == len(players):
            yield round

def is_canonical(player_count, games_played):
    played = [0] * player_count
    for players in games_played:
        for player in players:
            played[player] += 1

    return sorted(played) == played



def solve(court_count, player_count):
    courts = range(court_count)
    players = range(player_count)

    games = list( itertools.combinations(players, 2) )
    possible_rounds = list( rounds(games, court_count) )

    rounds_last = {}
    rounds_all = {}
    choices_last = {}
    choices_all = {}



    def update(target, choices, name, value, choice):
        try:
            current = target[name]
        except KeyError:
            target[name] = value
            choices[name] = choice
        else:
            if current > value:
                target[name] = value
                choices[name] = choice

    def solution(games_played, players, score, choice, last_players):
        games_played = frozenset(games_played)
        players = frozenset(players)

        choice = (choice, last_players)

        update(rounds_last.setdefault(games_played, {}), 
                choices_last.setdefault(games_played, {}), 
                players, score, choice)
        update(rounds_all, choices_all, games_played, score, choice)

    solution( [], [], 0, None, None)

    for games_played in subsets(games):
        if is_canonical(player_count, games_played):
            try:
                best = rounds_all[games_played]
            except KeyError:
                pass
            else:
                for next_round in possible_rounds:
                    next_games_played = games_played.union(next_round)

                    solution( 
                        next_games_played, to_players(next_round), best + 2,
                        next_round, [])

                for last_players, score in rounds_last[games_played].items():
                    for next_round in possible_rounds:
                        if not last_players.intersection( to_players(next_round) ):
                            next_games_played = games_played.union(next_round)
                            solution( next_games_played, to_players(next_round), score + 1,
                                    next_round, last_players)

    all_games = frozenset(games)


    print rounds_all[ all_games ]
    round, prev = choices_all[ frozenset(games) ]
    while all_games:
        print "X ", list(round)
        all_games = all_games - round
        if not all_games:
            break
        round, prev = choices_last[all_games][ frozenset(prev) ]

solve(2, 6)
 

Sortie:

 11
X  [(1, 2), (0, 3)]
X  [(4, 5)]
X  [(1, 3), (0, 2)]
X  []
X  [(0, 5), (1, 4)]
X  [(2, 3)]
X  [(1, 5), (0, 4)]
X  []
X  [(2, 5), (3, 4)]
X  [(0, 1)]
X  [(2, 4), (3, 5)]
 

Cela signifie qu'il faudra 11 tours. La liste montre les jeux à jouer dans les tours dans l'ordre inverse. (Bien que je pense que le même horaire fonctionne en avant et en arrière.) Je reviendrai et expliquerai pourquoi j'ai la chance.

Obtient des réponses incorrectes pour un terrain, cinq joueurs.

Answer 5

Certaines pensées, peut-être une solution...

Étendre le problème à X joueurs et Y tribunaux, je pense que nous pouvons dire en toute sécurité que quand donné le choix, nous devons choisir les joueurs avec le moins de terminé les matchs, sinon, nous courons le risque de se retrouver avec un joueur de gauche qui ne peut jouer à tous les autres de la semaine et nous nous retrouvons avec beaucoup de vide semaines entre les deux. Image le cas avec 20 joueurs et 3 courts. Nous pouvons voir que, au cours de la ronde 1 des joueurs 1-6 répondre, puis à la ronde 2 joueurs 7-12 rencontrer, et à la ronde 3, nous avons pu réutiliser les joueurs 1-6 laissant les joueurs 13-20 jusqu'à ce que plus tard. À cet effet, je pense que notre solution ne peut pas être gourmand et doit mettre en balance les joueurs.

Avec cette hypothèse, voici une première tentative de solution:

 1. Create master-list of all matches ([12][13][14][15][16][23][24]...[45][56].)
 2. While (master-list > 0) {
 3.     Create sub-list containing only eligible players (eliminate all players who played the previous round.)
 4.     While (available-courts > 0) {
 5.         Select match from sub-list where player1.games_remaining plus player2.games_remaining is maximized.
 6.         Place selected match in next available court, and 
 7.         decrement available-courts.
 8.         Remove selected match from master-list.
 9.         Remove all matches that contain either player1 or player2 from sub-list.
10.     } Next available-court
11.     Print schedule for ++Round.
12. } Next master-list

Je ne peux pas prouver que cela va produire un calendrier avec le moins de tours, mais il devrait être proche. L'étape qui peut causer des problèmes est #5 (sélectionner match qui maximise jeux de joueur restant.) Je peux imaginer qu'il pourrait y avoir un cas où il est préférable de choisir un match que presque maximise le "games_remaining" afin de laisser plus d'options dans le tour suivant.

La sortie de cet algorithme devrait ressembler à quelque chose comme:

Round    Court1    Court2
  1       [12]      [34]
  2       [56]       --
  3       [13]      [24]
  4        --        --
  5       [15]      [26]
  6        --        --
  7       [35]      [46]
  .         .         .

À proximité de l'inspection montrent que, dans la ronde 5, si le match sur Court2 avait été [23] puis match [46] pourrait avoir été joué lors de la ronde 6. Qui, cependant, ne garantit pas qu'il ne sera pas un problème similaire dans un cycle ultérieur.

Je travaille sur une autre solution, mais qui devra attendre pour plus tard.