Расписание матчей по теннису
Есть ограниченное количество игроков и ограниченное количество теннисных кортов. В каждом раунде может быть не больше, чем количество матчей. Никто не играет 2 раунда без перерыва. Все играют матч против всех остальных. Составьте расписание, которое займет как можно меньше раундов. (Из-за правила, согласно которому должен быть перерыв между раундами для всех, может быть раунд без матчей.) Выход для 5 игроков и 2 кортов может быть:
| 1 2 3 4 5
-|-------------------
2| 1 -
3| 5 3 -
4| 7 9 1 -
5| 3 7 9 5 -
В этих выходных данных столбцы и строки представляют собой номера игроков, а числа внутри матрицы - это круглые числа, в которых соревнуются эти два игрока.
Проблема состоит в том, чтобы найти алгоритм, который может сделать это для больших экземпляров за приемлемое время. Нас попросили сделать это на прологе, но (псевдо) код на любом языке был бы полезен.
Моя первая попытка была жадным алгоритмом, но он дает результаты с большим количеством раундов. Затем я предложил итеративный углубленный поиск в глубину, который реализовал мой друг, но он все еще занимал слишком много времени в случаях с 7 игроками.
(Это из старого экзаменационного вопроса. Никто, с кем я говорил, не имел никакого решения.)
6 ответов
Предисловие
В 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 минуты:
? - время (теннис (6, 2, ряды)),
MapList (формат ("~ т ~ ш ~3+~ т ~ ш ~3+~ т ~ ш ~3+~ т ~ ш ~3+~ т ~ ш ~3+~ т ~ ш ~3+\ п"), Ряды).
% 6 675 665 выводов, 0,970 ЦП за 0,977 секунды (99% ЦП, 6884940 губ)
- 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 кортах:
? - время (теннис (7, 5, рядов)),
MapList (формат ("~ т ~ ш ~3+~ т ~ ш ~3+~ т ~ ш ~3+~ т ~ ш ~3+~ т ~ ш ~3+~ т ~ ш ~3+~ т ~w~3+\n"), ряды).
% 125 581 090 выводов, 17,476 процессора за 18,208 секунды (96% процессора, 7185927 губ)
- 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 (библиотека (списки)).:- use_module(библиотека (между)).:- op(700, xfx, ins).
Vs ins D:- список карт (in_(D), Vs).
in_(D, V):- V в D.
цепочка ([], _).
цепь ([L|Ls], пред): -
Цепочка_(Ls, L, Pred).
цепочка _([], _, _).
цепочка _([L|Ls], предыдущий, предыдущий): -
вызов (Pred, Prev, L),
Цепочка_(Ls, L, Pred).
pair_keys_values (Ps, Ks, Vs):- keys_and_values (Ps, Ks, Vs).
Foldl (Пред, Ls1, Ls2, Ls3, S0, S):-
foldl_(Ls1, Ls2, Ls3, Pred, S0, S).
свернуть _([], [], [], _, S, S).
foldl_([L1|Ls1], [L2|Ls2], [L3|Ls3], Pred, S0, S):-
вызов (Пред, L1, L2, L3, S0, S1),
foldl_(Ls1, Ls2, Ls3, Pred, S1, S).
время (гол): -
статистика (время выполнения, [T0|_]),
звоните (цель),
статистика (время выполнения, [T1|_]),
Т #= Т1 - Т0,
формат ("% Runtime: ~Dms\n", [T]).
Основное отличие: SICStus, будучи Prolog коммерческого уровня, который поставляется с серьезной системой CLP(FD), намного быстрее, чем SWI-Prolog в этом случае использования и других подобных.
Указанное задание 6 игроков на 2 кортах:
? - время (теннис (6, 2, ряды)),
MapList (формат ("~ т ~ ш ~3+~ т ~ ш ~3+~ т ~ ш ~3+~ т ~ ш ~3+~ т ~ ш ~3+~ т ~ ш ~3+\ п"), Ряды).
% Времени выполнения: 34 мс (!)
- 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 -
Большой пример:
|? - время (теннис (7, 5, рядов)),
MapList (формат ("~ т ~ ш ~3+~ т ~ ш ~3+~ т ~ ш ~3+~ т ~ ш ~3+~ т ~ ш ~3+~ т ~ ш ~3+~ т ~w~3+\n"), ряды).
% Времени выполнения: 884мс
- 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.
Это очень похоже на задачу Traveling Tournament, которая касается планирования футбольных команд. В TTP они могут найти оптимальное решение только для 8 команд. Любому, кто побьет рекорд из 10 или более команд, намного легче опубликовать его в исследовательском журнале.
Это трудная задача, и хитрость заключается в том, чтобы использовать метаэвристику, такую как поиск по табу, имитированный отжиг,... вместо грубой силы или ветвления и ограничения.
Посмотрите мою реализацию с Drools Planner (с открытым исходным кодом, Java). Вот ограничения, должно быть просто заменить это на ограничения, такие как Никто не играет 2 раунда без перерыва.
Каждый игрок должен сыграть не менее n - 1 матчей, где n - количество игроков. Таким образом, минимум раундов составляет 2(n - 1) - 1, так как каждый игрок должен отдохнуть матч. Минимум также ограничен (n(n-1))/2 совпадениями, разделенными на количество судов. Использование наименьшего из этих двух дает вам длину оптимального решения. Затем нужно придумать хорошую более низкую формулу оценки ((количество совпадений + оставшихся мест) / корты) и запустить поиск A *.
Как сказал Джеффри, я считаю, что проблема в NP Hard, но метаэвристика, такая как A *, очень применима.
Решение 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 раундов. Список показывает игры, в которые нужно играть в раундах, в обратном порядке. (Хотя я думаю, что тот же график работает вперед и назад.) Я вернусь и объясню, почему у меня есть такая возможность.
Получает неверные ответы для одного корта, пяти игроков.
Некоторые мысли, возможно решение...
Рассматривая проблему для 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-м раунде, если бы матч на Court2 был [23], то матч [46] мог бы быть сыгран в течение 6-го раунда. Однако это не гарантирует, что подобной проблемы не будет в более поздний раунд.
Я работаю над другим решением, но это придется подождать позже.
Я не знаю, имеет ли это значение, в данных примера "5 игроков и 2 суда" пропущены три других матча: [1,3], [2,4] и [3,5]. На основании инструкции: "Каждый играет против всех остальных".