#algorithm #optimization #combinatorics
#алгоритм #оптимизация #комбинаторика
Вопрос:
Предыстория
Спортивный клуб, в котором я участвую, попросил меня помочь с некоторой ИТ-поддержкой для предстоящего соревнования.
В соревновании участвуют команды, точное количество которых не обязательно известно до дня соревнований. Отсюда необходимость в помощи программного обеспечения.
Все команды встретятся с любой другой командой в нескольких матчах. Таким образом, количество совпадений составляет N больше 2 (все комбинации по 2), где N — количество команд.
У нас есть неизвестное количество доступных кортов для проведения матчей. Вероятно, это число будет равно 1 или, возможно, 2, но я хотел бы общее решение.
Соревнование будет проходить по очереди. В каждый ход на каждом корте будет сыгран один матч.
Например, если есть два корта и пять команд (A, B, C, D, E), схема хода может выглядеть следующим образом:
Переверните корт 1 Корт 2 -------------------------------- 1 A vs B C vs D 2 A vs C D vs E 3 A vs D B vs E 4 B vs D C vs E 5 A vs E B vs C
Проблема
Таким образом, моя проблема заключается в том, чтобы найти алгоритм для генерации набора поворотов, которые подчиняются следующим простым правилам:
- Все команды должны встретиться со всеми другими командами ровно один раз в течение соревнования.
- Команда не может сыграть два матча в один ход (т.е. она не может играть одновременно на кортах 1 и 2)
- Ходы, в которых играет конкретная команда, должны быть распределены по всему соревнованию.
Правило 3 в деталях
Правила 1 и 2 довольно просты, и у меня уже есть решение для этого. Это правило 3, которое вызывает у меня проблемы. Я попытаюсь показать, что это значит:
Допустим, у меня 5 команд (как указано выше), но только 1 корт. За 10 ходов происходит 10 совпадений. Одним из возможных вариантов является
Терн корт 1 1 A против B 2 A против C 3 A против D 4 A против E 5 . . . . . 10 .
В этом случае A играет первые четыре матча, что несправедливо, поскольку у них нет возможности восстановить свои силы между играми. Это то, чего я хочу избежать.
Идеи?
Ответ №1:
Как насчет простого решения с жадностью, где у вас есть значение усталости для каждой команды.
Сначала усталость для всех команд устанавливается равной 0. На терне № 1 проведите начальный матч для разных кортов и установите значение усталости для этих команд таким же, как на текущем терне (1 в первом матче).
По очереди № 2 выберите команды с наименьшей усталостью (например, сохраняя команды в приоритетной очереди), которые не играли друг с другом, и сопоставьте их. Установите значение усталости равным текущему значению оборотов.
В вашем примере вы получите:
Turn Court 1 Team:fatigue
0 - A:0 B:0 C:0 D:0 E:0
1 A vs B C:0 D:0 E:0 A:1 B:1
2 C vs D E:0 A:1 B:1 C:2 D:2
3 E vs A B:1 C:2 D:2 E:3 A:3
4 B vs C D:2 E:3 A:3 B:4 C:4
5 D vs E A:3 B:4 C:4 D:5 E:5
6 A vs C B:4 D:5 E:5 A:6 C:6 // Dont match A with B since they already played, jump to team C
.
Всегда выводить свежие команды на старт. Поскольку у вас, вероятно, не будет более 100 команд, этого должно быть достаточно.
Комментарии:
1. Это хорошая идея. И я думаю, вы можете избавиться от значения усталости, если будете продолжать удалять команды, которые попали под действие match, и помещать их в конец списка.
2. @sawa это правда, поскольку свежие команды всегда будут впереди.
3. Я попробовал что-то подобное, и получил несколько странных результатов. Я попробую это снова. Приоритетная очередь звучит достаточно просто.
Ответ №2:
Ленивый подход заключается в использовании вашего текущего решения, затем рандомизируйте временные интервалы (строки в вашей презентации) X раз, отслеживая некоторый критерий утомления и сохраняя лучшее решение, найденное на данный момент. При использовании других решений вам нужно быть осторожным, чтобы вы могли полностью использовать все корты.
Комментарии:
1. Обратите внимание, что ход не определяется независимо от всего алгоритма. Ставить совпадения AB и CD под один ход или ставить AB и CE под один может иметь последствия. Я не понял вашего последнего предложения.
2. Это немного расплывчато для меня, чтобы было что тестировать. Я рассматривал возможность использования генетического алгоритма, но создать функцию соответствия было довольно сложно, поэтому я отказался от этого.
3. @kigurai вы написали «Правила 1 и 2 довольно просты, и у меня уже есть решение для этого», поэтому я предположил, что вы можете получить решение, как в вашем первом примере. Затем, чтобы минимизировать утомляемость, вы можете просто переставить строки такого решения.
4. @sawa. При стратегиях, в которых вы выбираете матчи на основе усталости, вы можете оказаться, например, в ситуации, когда осталось два корта и в двух играх участвуют только три команды. Итак, вы должны быть либо умными, либо вызвать отслеживание возврата.
5. @micans: на самом деле усталость не обязательно «удаляет» команду, она может просто отсортировать их так, чтобы у более свежих было больше шансов сыграть, и в этом случае вам никогда не «не хватает» команды.