Я пытаюсь создать планировщик спортивной лиги. У меня проблемы с определением алгоритма, который поможет мне эффективно заполнить каждый слот.
Пример данных для построения графика будет:
- 10 команд
- Каждая команда играет друг с другом 1 раз (требуется 45 игр)
- Каждая команда играет не более 1 раза в день
- В своем тестировании я использую 9 дней с 5 слотами в день.
Комбинированный стол (содержит 45 комбинаций)
ID
Team1ID
Team2ID
bitAssigned
Таблица расписаний (содержит 45 временных интервалов)
scheduleID
homeTeamID
awayTeamID
GameDate
GameTime
Прямо сейчас мои существующие процедуры заполняют около 90% слотов, оставляя 10% моих слотов пустыми из-за конфликта планирования, основанного на правилах выше.
Я перебираю таблицу расписания в порядке возрастания даты / времени.
Мой первый слот может быть в субботу в 8 утра.
Я запрашиваю список команд, которые еще не запланированы. Затем я делаю множество возможных комбинаций этих команд. Затем я использую этот массив для извлечения 1 случайной записи из моей таблицы комбинаций из комбинаций, которые еще не были запланированы, и помещаю эти команды в расписание. Затем я установил эту комбинацию как использованную.
Я повторяю цикл снова и снова, и каждый раз мой список доступных команд уменьшается, и мой массив в результате также уменьшается.
Я обнаружил, что некоторые дни проходят хорошо, а в другие дни мои последние две оставшиеся команды уже играли на предыдущей неделе, поэтому они больше не добавляются в расписание.
Единственное, что я еще не пробовал, - это «перезагрузить» дни конфликта и перепробовать их снова, чтобы посмотреть, получу ли я лучшие места размещения.
У кого-нибудь есть предложения?
источник
Ответы:
Вот алгоритм, который я придумал сам. Я не знаю, существует ли он уже или является циклической реализацией:
в основном вы начинаете с
и всегда держите 1 в том же положении и вращайте остальные.
Таким образом, вы всегда получите расписание уникальных матчей. Это очень легко реализовать и масштабируется с любым количеством противников, даже или неравномерно. Если у вас неравное количество противников, просто не ставьте команду на 1 позицию, и у них есть свободный раунд.
источник
Я думаю, что вы делаете это задом наперед. Не начинайте с таблицы расписания, начните с таблицы / массива / любой другой игровой комбинации (45 игр). Оттуда это простой процесс назначения игр на один день, основанный на команде, играющей только один раз в день. А поскольку совпадения происходят только один раз (команда A играет только команду B один раз), планирование легко, потому что вам просто нужно убедиться, что совпадение еще не произошло (записи «уникальны» таким образом).
источник
Я сформировал расписание из 10 команд в одиночном раунде ниже. Это заняло у меня около 3 минут.
Информация о расписании:
10 команд - 1 круговая
игра ( отображаются только первые 6 недель) Дата начала сезона 1/6/15 - дата окончания 3/5/15
2 игры каждый вторник, 3 игры каждый четверг, 5 игр каждую неделю без пропущенных дат
Мы использовали устаревший основной компьютер Honeywell и чуть менее 3 лет, чтобы собрать все это вместе. После отладки нашего программного обеспечения для планирования потребовалось много часов, чтобы главный компьютер поиска искал миллионы комбинаций и комбинаций, чтобы рассчитать и создать сбалансированные шаблоны для 4–22 команд, которые мы искали.
Не существует алгоритма, который решает общие проблемы планирования, связанные с сотнями или тысячами различных типов лиг, видов спорта и потенциальных ситуаций. Что мы сделали, чтобы решить эту проблему, так это использовать другой подход для расчета расписаний. Он начинается с очень сложной математики, чтобы определить правильные парные команды (матчи), но это было только начало. Другие части необходимы для создания полезного сбалансированного графика, который можно публиковать и распространять. Игроки, тренеры, родители и т. Д., Все должны знать не только, кого они играют ; но где они играют ; во сколько они играют ; если они дома или в гостях ; и для многих лиг, номер игры .
Я надеюсь, что это поможет вам и другим понять, что нам понадобилось 3 года, чтобы понять.
источник