Как расставить пары с условием за преемлемое время (380! комбинаций)?

Есть 20 команд которые должны играть с друг другом парами (1 - 4 раза), т.е. итого 20*19 = 380 матчей (при 2х играх для пары).
Есть несколько свободных слот на каждый день - т.е. место и время
Условие: если команда играет в этот день, то у неё должно быть минимум 2 игры (не должно быть ровно одной игры в день), либо 0 либо 2+ игры.

Как найти расстановку матчей (расписание) при минимальном кол-ве дней (либо приемлемый результат, минимальный + 10%), за приемлемое время?

Если просто перебирать все варианты то это 380! что не реально проверить.
Я сделал решение которое делает расстановку за O(N*M) (матчи х слоты), методом решета и спроса, но без условия "минимум 2 игры в день".

Если применить условие, то мой алгоритм не находит решения.
Куда копать, какие есть варианты?

Сейчас в голове 2 направления:
* Рекурсивный перебор + оптимизации (какие? те же отсечения решета и спроса?)
* Сделать готовые патерны расстановок и применять их
  • Вопрос задан
  • 227 просмотров
Решения вопроса 1
Или я не понял условие или...
А что здесь какого-то сложного? Минимальное количество дней обеспечит максимальная загрузка слотов ежедневно.
Если слотов четное количество (n). То на каждом шаге выбираем n/2 пар которые еще не играли и они отыгрывают обе свои игры.

Если слотов нечетное количество то на нечетном шаге выбираем (n-1)/2 пар которые еще не играли и они отыгрывают обе свои игры + 1 пару которая еще не играла и она играет 1 игру.
На четном шаге мы выбираем (n-1)/2 пар которые еще не играли и они отыгрывают обе свои игры и одну единственную пару которая сыграла свою одну игру на прошлом шаге - она отыгрывает вторую свою игру.

Всё.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы