algorithm - torneos - final de tenis hoy horario

Programación de partidos de tenis

Question

Hay un número limitado de jugadores y un número limitado de canchas de tenis. En cada ronda, puede haber como máximo tantos partidos como canchas. Nadie juega 2 rondas sin descanso. Todos juegan un partido contra todos los demás. Produzca el programa que requiere la menor cantidad de rondas posible. (Debido a la regla de que debe haber un descanso entre rondas para todos, puede haber una ronda sin partidos). La salida para 5 jugadores y 2 canchas podría ser:

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

En esta salida, las columnas y las filas son los números de jugador, y los números dentro de la matriz son los números redondos que compiten estos dos jugadores.

El problema es encontrar un algoritmo que pueda hacer esto para instancias más grandes en un tiempo factible. Nos pidieron que hiciéramos esto en Prolog, pero el (pseudo-) código en cualquier idioma sería útil.

Mi primer intento fue un algoritmo codicioso, pero eso da resultados con demasiadas rondas. Luego, sugerí una búsqueda de profundización iterativa en profundidad, que un amigo mío implementó, pero que aún requería demasiado tiempo en instancias tan pequeñas como 7 jugadores.

(Esto es de una vieja pregunta del examen. Nadie con quien hablé tenía ninguna solución).

Answer 1

Prefacio

En Prolog, las restricciones CLP (FD) son la elección correcta para resolver tales tareas de programación.

Ver clpfd para más información.

En este caso, sugiero usar la poderosa restricción global_cardinality/2 para restringir el número de apariciones de cada ronda, dependiendo de la cantidad de pistas disponibles. Podemos usar profundización iterativa para encontrar el número mínimo de rondas admisibles.

Los sistemas Prolog libremente disponibles son suficientes para resolver la tarea satisfactoriamente. Los sistemas de grado comercial se ejecutarán docenas de veces más rápido.

Variante 1: Solución con SWI-Prolog

:- use_module(library(clpfd)).

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

triangle(Row, Vs, Ds, N0, N) :-
        length(Prefix, N0),
        append(Prefix, [-|Vs], Row),
        append(Prefix, Vs, Ds),
        N #= N0 + 1.

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

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

Consulta de muestra: 5 jugadores en 2 pistas:

?- 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,-]

La tarea especificada, 6 jugadores en 2 pistas , se resolvió bien dentro del límite de tiempo de 1 minuto:

?- time(tennis(6, 2, Rows)), maplist(format("~t~w~3+~t~w~3+~t~w~3+~t~w~3+~t~w~3+~t~w~3+/n"), Rows). % 6,675,665 inferences, 0.970 CPU in 0.977 seconds (99% CPU, 6884940 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 -

Ejemplo adicional: 7 jugadores en 5 pistas:

?- time(tennis(7, 5, Rows)), maplist(format("~t~w~3+~t~w~3+~t~w~3+~t~w~3+~t~w~3+~t~w~3+~t~w~3+/n"), Rows). % 125,581,090 inferences, 17.476 CPU in 18.208 seconds (96% CPU, 7185927 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 -

Variante 2: solución con SICStus Prolog

Con las siguientes definiciones adicionales de compatibilidad, el mismo programa también se ejecuta en SICStus Prolog:

:- use_module(library(lists)). :- use_module(library(between)). :- op(700, xfx, ins). Vs ins D :- maplist(in_(D), Vs). in_(D, V) :- V in D. chain([], _). chain([L|Ls], Pred) :- chain_(Ls, L, Pred). chain_([], _, _). chain_([L|Ls], Prev, Pred) :- call(Pred, Prev, L), chain_(Ls, L, Pred). pairs_keys_values(Ps, Ks, Vs) :- keys_and_values(Ps, Ks, Vs). foldl(Pred, Ls1, Ls2, Ls3, S0, S) :- foldl_(Ls1, Ls2, Ls3, Pred, S0, S). foldl_([], [], [], _, S, S). foldl_([L1|Ls1], [L2|Ls2], [L3|Ls3], Pred, S0, S) :- call(Pred, L1, L2, L3, S0, S1), foldl_(Ls1, Ls2, Ls3, Pred, S1, S). time(Goal) :- statistics(runtime, [T0|_]), call(Goal), statistics(runtime, [T1|_]), T #= T1 - T0, format("% Runtime: ~Dms/n", [T]).

Diferencia importante: SICStus, al ser un Prolog de grado comercial que se envía con un sistema CLP (FD) serio, es mucho más rápido que SWI-Prolog en este caso de uso y otros similares.

La tarea especificada, 6 jugadores en 2 pistas:

?- time(tennis(6, 2, Rows)), maplist(format("~t~w~3+~t~w~3+~t~w~3+~t~w~3+~t~w~3+~t~w~3+/n"), Rows). % Runtime: 34ms (!) - 1 3 5 7 10 1 - 6 11 9 3 3 6 - 9 11 1 5 11 9 - 2 7 7 9 11 2 - 5 10 3 1 7 5 -

El ejemplo más grande:

| ?- time(tennis(7, 5, Rows)), maplist(format("~t~w~3+~t~w~3+~t~w~3+~t~w~3+~t~w~3+~t~w~3+~t~w~3+/n"), Rows). % Runtime: 884ms - 1 3 5 7 9 11 1 - 5 3 9 7 13 3 5 - 1 11 13 7 5 3 1 - 13 11 9 7 9 11 13 - 3 1 9 7 13 11 3 - 5 11 13 7 9 1 5 -

Observaciones finales

En ambos sistemas, global_cardinality/3 permite especificar opciones que alteran la fuerza de propagación de la restricción de cardinalidad global, lo que permite un filtrado más débil y potencialmente más eficiente. Elegir las opciones correctas para un ejemplo específico puede tener un impacto aún mayor que la elección del sistema Prolog.

Answer 2

Algunos pensamientos, tal vez una solución ...

Ampliando el problema a X jugadores y Y tribunales, creo que podemos decir con seguridad que cuando se les da la opción, debemos seleccionar los jugadores con el menor número de partidos completados, de lo contrario corremos el riesgo de terminar con un jugador que solo puede jugar cada otra semana y terminamos con muchas semanas vacías en el medio. Imagínate el caso con 20 jugadores y 3 canchas. Podemos ver que durante la ronda 1 los jugadores 1-6 se encuentran, luego en la ronda 2 los jugadores 7-12 se encuentran, y en la ronda 3 podemos reutilizar los jugadores 1-6 dejando a los jugadores 13-20 hasta más adelante. Por lo tanto, creo que nuestra solución no puede ser codiciosa y debe equilibrar a los jugadores.

Con esa suposición, aquí hay un primer intento de solución:

 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

No puedo probar que esto producirá un cronograma con la menor cantidad de rondas, pero debería estar cerca. El paso que puede causar problemas es el n. ° 5 (selección de partidos que maximiza los juegos restantes del jugador). Puedo imaginar que podría haber un caso en el que sea mejor elegir una partida que casi maximice la "recuperación de juegos" para dejar más opciones en el siguiente redondo.

El resultado de este algoritmo sería algo así como:

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

Una inspección cercana mostrará que en la ronda 5, si el partido en Court2 había sido [23], entonces match [46] podría haberse jugado durante la ronda 6. Sin embargo, eso no garantiza que no habrá un problema similar en una ronda posterior.

Estoy trabajando en otra solución, pero eso tendrá que esperar más tarde.

Answer 3

Cada jugador debe jugar al menos n - 1 partidos donde n es el número de jugadores. Entonces el mínimo de rondas es 2 (n - 1) - 1, ya que cada jugador necesita descansar un partido. El mínimo también está limitado por (n (n-1)) / 2 coincidencias totales dividido por el número de cortes. Usar el más pequeño de estos dos le da la duración de la solución óptima. Luego, se trata de obtener una buena fórmula de estimación inferior ((número de coincidencias + restos restantes) / canchas) y ejecutar A * búsqueda .

Como dijo Geoffrey, creo que el problema es NP Duro, pero la meta-heurística como A * es muy aplicable.

Answer 4

Esto es muy similar al problema del torneo itinerante , que se trata de programar equipos de fútbol. En TTP, pueden encontrar la solución óptima solo para 8 equipos. Cualquier persona que rompa un registro continuo de 10 o más equipos, tiene mucho más fácil ser publicado en un diario de investigación.

Es NP difícil y el truco es usar metaheurísticas, como la búsqueda tabú, el recocido simulado, ... en lugar de la fuerza bruta o la ramificación y el límite.

Echa un vistazo a mi implementación con Drools Planner (código abierto, java). Aquí están las restricciones , debería ser sencillo reemplazar eso con restricciones como Nadie juega 2 rondas sin descanso.

Answer 5

No sé si esto importa, los datos de ejemplo de "5 jugadores y 2 tribunales" faltan otros tres partidos: [1,3], [2,4] y [3,5]. Basado en las instrucciones: "Todos juegan un partido contra todos los demás".

Answer 6

Solución de 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)

Salida:

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)]

Esto significa que tomará 11 rondas. La lista muestra los juegos que se jugarán en las rondas en orden inverso. (Aunque creo que el mismo horario funciona hacia delante y hacia atrás.) Volveré y explicaré por qué tengo la oportunidad.

Obtiene respuestas incorrectas para un tribunal, cinco jugadores.