Расписание матчей по теннису

Question

Есть ограниченное количество игроков и ограниченное количество теннисных кортов.В каждом раунде может быть не больше, чем количество матчей.Никто не играет 2 раунда без перерыва.Все играют матч против всех остальных.Составьте расписание, которое займет как можно меньше раундов.(Из-за правила, согласно которому должен быть перерыв между раундами для всех, может быть раунд без матчей.) Выходные данные для 5 игроков и 2 кортов могут быть:

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

.строки - это номера игроков, а числа внутри матрицы - это круглые числа, в которых соревнуются эти два игрока.

Проблема состоит в том, чтобы найти алгоритм, который может сделать это для больших экземпляров за приемлемое время.Нас попросили сделать это в Прологе, но (псевдо-) код на любом языке был бы полезен.

Моя первая попытка была жадным алгоритмом, но он дает результаты с большим количеством раундов.Затем я предложил итеративный углубленный поиск в глубину, который реализовал мой друг, но он все еще занимал слишком много времени на экземплярах размером до 7 игроков.

(Это из старого экзаменационного вопроса.Я говорил, было какое-либо решение.)

Answer 1

Введение

В Prolog ограничения CLP (FD) являются правильным выбором для решения таких задач планирования.

См. clpfd для получения дополнительной информации.

В этом случае я предлагаю использовать мощное ограничение global_cardinality/2, чтобы ограничить число случаев каждого раунда, в зависимости от количества доступных судов. Мы можем использовать итеративное углубление , чтобы найти минимальное количество допустимых раундов.

Свободно доступных систем Prolog достаточно для удовлетворительного решения задачи. Системы коммерческого уровня будут работать в десятки раз быстрее.

Вариант 1: решение с 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.

Пример запроса: 5 игроков на 2 кортах:

?- 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 игроков на 2 кортах , хорошо решена в течение 1 минуты:

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

Еще пример: 7 игроков на 5 кортах:

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

Вариант 2: решение с помощью SICStus Prolog

Со следующими дополнительными определениями совместимости, та же самая программа также запускается в 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]).

Основное отличие: SICStus, будучи Prolog коммерческого уровня, который поставляется с серьезной системой CLP (FD), на намного быстрее , чем SWI-Prolog в этом случае использования и других подобных ему.

Указанное задание, 6 игроков на 2 кортах:

?-   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).
% <b>Runtime: 34ms (!)</b>
  -  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  -

Более крупный пример:

| ?- 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).
% <b>Runtime: 884ms</b>
  -  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  -

Заключительные замечания

В обеих системах global_cardinality/3 позволяет указывать параметры, которые изменяют степень распространения глобального ограничения мощности, обеспечивая более слабую и потенциально более эффективную фильтрацию. Выбор правильных опций для конкретного примера может иметь еще большее влияние, чем выбор системы Prolog.

Answer 2

Это очень похоже на проблему Travel Tournament , которая касается планирования футбольных команд. В TTP они могут найти оптимальное решение только для 8 команд. Любому, кто побьет рекорд из 10 или более команд, намного легче опубликовать его в исследовательском журнале.

Это NP трудный, и хитрость заключается в том, чтобы использовать метаэвристику, такую ​​как поиск по табу, имитированный отжиг, ... вместо грубой силы или ветвления и ограничения.

Взгляните моя реализация с Drools Planner (с открытым исходным кодом, Java). Вот ограничения , заменить их на такие ограничения просто: Никто не играет 2 раунда без перерыва.

Answer 3

Каждый игрок должен сыграть не менее n - 1 матчей, где n - количество игроков.Таким образом, минимум раундов составляет 2 (n - 1) - 1, так как каждый игрок должен отдохнуть матч.Минимум также ограничен (n (n-1)) / 2 совпадениями, разделенными на количество судов.Использование наименьшего из этих двух дает вам оптимальное решение.Затем нужно придумать хорошую более низкую формулу оценки ((количество совпадений + оставшихся остатков) / корты) и запустить A * search .

Как сказал Джеффри, я считаю, что проблема в NP Hard, но метаэвристика, такая как A *, очень применима.

Answer 4

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)

Вывод:

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

Это означает, что потребуется 11 раундов.Список показывает игры, в которые нужно играть в раундах, в обратном порядке.(Хотя я думаю, что тот же график работает вперед и назад.) Я вернусь и объясню, почему у меня есть шанс.

Получает неправильные ответы для одного корта, пяти игроков.

Answer 5

Некоторые мысли, возможно, решение ...

Расширяя задачу для X игроков и Y кортов, я думаю, что мы можем с уверенностью сказать, что когда нам предоставляется выбор, мы должны выбирать игроков с наименьшим количеством завершенных матчей, в противном случае мы рискуем оказаться с одним оставшимся игроком, который может играйте только раз в две недели, и в итоге у нас будет много пустых недель. Представьте себе случай с 20 игроками и 3 кортами. Мы видим, что в течение первого раунда встречаются игроки 1-6, затем во втором раунде встречаются игроки 7-12, а в третьем раунде мы можем повторно использовать игроков 1-6, оставляя игроков 13-20 до позднего времени. Поэтому я думаю, что наше решение не может быть жадным и должно уравновешивать игроков.

С этим допущением, вот первая попытка решения:

 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

Я не могу доказать, что это даст расписание с наименьшим количеством раундов, но оно должно быть близко. Шаг, который может вызвать проблемы, # 5 (выберите матч, который максимизирует оставшееся количество игр игрока.) Я могу себе представить, что может быть случай, когда лучше выбрать матч, который почти максимизирует "games_remaining", чтобы оставьте больше вариантов в следующем раунде.

Вывод этого алгоритма будет выглядеть примерно так:

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

При ближайшем рассмотрении будет показано, что в 5-м раунде, если матч на Корт2 был [23], то матч [46] мог быть сыгран в течение 6-го раунда. Однако это не гарантирует, что не будет аналогичная проблема в более позднем раунде.

Я работаю над другим решением, но это придется подождать позже.

Answer 6

Не знаю, имеет ли это значение, в данных примера «5 игроков и 2 суда» пропущены три других матча: [1,3], [2,4] и [3,5]. На основании инструкции: «Каждый играет против всех остальных».