Ответ 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 игроков на двух судах:

?- 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).
% 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  -

Пример:

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

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

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

Ответ 2

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

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

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

Ответ 3

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

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

Ответ 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 раундов. В списке показаны игры, которые будут воспроизводиться в раундах в обратном порядке. (Хотя я думаю, что одно и то же расписание работает вперед и назад). Я вернусь и объясню, почему у меня есть шанс.

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

Ответ 5

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

Развернув проблему для игроков X и Y судов, я думаю, мы можем с уверенностью сказать, что, когда вы даете выбор, мы должны выбрать игроков с наименьшим количеством завершенных матчей, иначе мы рискуем оказаться с одним игроком слева, который может играйте каждую неделю, и в итоге мы получаем много пустых недель. Представьте пример с 20 игроками и тремя судами. Мы видим, что во время раунда 1 игроки 1-6 встречаются, затем в раунде 2 игроки 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, если матч на Court2 был [23], тогда матч [46] мог быть сыгран во время раунда 6. Это, однако, не гарантирует, что не будет аналогичная проблема в более позднем раунде.

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

Ответ 6

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