Жеребьевка. Максимально развести участников соревнований от повторов

Здравствуйте!
Есть некий вид авиамодельного спорта - Воздушный бой радиоуправляемых моделей самолетов.
Для автоматизации проведения стартов, мною написана программа, некий АРМ секретаря стартов.(Как конфигурация 1С, но, это не принципиально, на чем мне проще было написать, на том и сделал, сути задачи это не меняет)
Программа охватывает практически все аспекты организации стартов, подсчета итогов соревнований и т.д...
Самый сложный и проблемный модуль программы - это жеребьевка.
В файле вложения, подробное описание задачи, с необходимыми для ее понимания примерами-таблицами.
Сейчас у меня ее алгоритм решен путем простого перебора комбинаций, с проверкой всех необходимых условий. До определенного времени, когда количество участников соревнований было порядка 40 и более, проблем не возникало - комбинаций было огромное число, и решение обычно находилось. Сейчас, в связи с кризисом, средний размер этапа стал 20-25 человек. И в такой ситуации, перебором уже не получается, надо придумать что-то более "научное", но, у меня к сожалению знаний в этой области не хватает... Очень прошу знающих людей помочь, дать "толчек", направление построения алгоритма, а дальше, я уже напишу код...
В кратце, условия задачи:
Константы:
1. Количество стартовых позиций - всегда 4.
2. Количество туров - всегда 4.
Переменные:
1. Количество участников: От 8 и до.... бесконечности, на практике, 15 - 35.
2. Количество команд: от 1 и до Количества участников(если вдруг все команды будут состоять из 1 участника, чего, конечно на практике не бывает, обычно от 2 до 6).
3. Количество членов команды: аналогично с предыдущим, от 1 и до Количества участников, если команда одна(чего на практике, конечно не бывает, так же от 2 и до 6-7).
Переменные 2 и 3 можно представить как один массив, с размером равным количеству команд, а каждый элемент которого, это команда с размером равным количеству членов команды.
Условия:
1. Каждый участник должен отлетать 4 тура, по одному разу в каждом туре на одной стартовой позиции.
2. В одном бою надо развести по максимуму членов одной команды.
3. В течении всех 4-х туров, надо минимизировать количество повторов пересечений участников между собой.

На выходе, нужно получить таблицу боев, на все 4 тура, с распределением участников согласно условий...
Первые два условия, у меня и так сейчас выполняются, а вот третье неудовлетворительно...
Надо как-то подсчитать, на основе входных данных, возможный результат(минимально-возможное количество повторов), и естественно получить конечную цель - таблицу жеребьевки...
В файле-вложения подробно все расписано, и приведены таблицы одного из реальных этапов, с интересными комбинациями переменных. Результат - 7 повторов. Я чувствую, что это не предел, если более грамотно подойти к решению этой задачи.

Да... По ходу, сложная задача... Или не интересная? Или описал плохо?
В файле, описание значительно подробнее, с "расшифровкой" терминов, объяснением что и почему так, а не иначе, с таблицами примеров на основе реальных соревнований...
Но, количество просмотров файла, за почти сутки - 1...
Напишите, хоть что не так? Может не в тему? Это не комбинаторика? Тогда, подскажите, что? В другом разделе задам вопрос...

Вложения

Описание жеребьевки RCCR.docx (32.1 Кб, 12 просмотров)

0

0

Вот, во вложении - файлы экселя на текущий момент, что у меня получаются...
Хочется понять - это максимум, что возможно, или все-таки есть еще варианты?

По моему алгоритму, очень сильная зависимость от начального расположения строк в исходной таблице...
Связано с разным размером и составом команд... Пробовал делать сортировку по размеру команд, в обе стороны, и по убыванию, и по возрастанию - бесполезно... Только хуже, чем та комбинация, которая случайно согласно занятых мест выстроилась... При таком расположении - 5 повторов, при сортировках 10 и 7, в зависимости от направления сортировки... Уловить какую-то закономерность, мне не удалось, поэтому задал цикл из 30 повторов с перемешиванием исходного списка с помощью генератора случайных чисел, с запоминанием лучшего достигнутого результата и выводом потом, после завершения, его... В случае удачи - разведения без повторов, цикл естественно прерывается и выводится результат. Почему 30? Из соображений разумного времени выполнения... И так, это делается, минут около 5-ти, на моем
компе, на ноутбуке, в поле, будет дольше... После отработки этого алгоритма, остается 4 повтора... Значит, все-таки есть комбинация исходных строк, лучше, чем изначальная...
ГСЧ, в этом случае - не верное решение, надо как-то избежать его использования, так, как комбинации могут повторяться, тратя время в никуда... Перебрать все варианты перестановок исходного списка, с запоминанием лучшего результата - тоже не реально, при 25 участниках, как я понимаю(может ошибаюсь?), это будет 25 в 25 степени... Это на неделю работа
даже на хорошем компе... Нужно какой-то другой принцип...
За исходную таблицу взята таблица реальных соревнований, но на момент после их завершения. То-есть, участники в таблице выстроились согласно занятых мест. На самом деле, на момент проведения жеребьевки(после завершения регистрации участников), строки в исходной таблице располагаются так, как заносит их секретарь стартов - по мере того, как подходят участники на регистрацию. Чаще всего, регистрируют по командам - подходит один представитель команды, и регистрирует сразу всех ее членов. Естественно, все это в разнобой, никак не связано ни с какими условиями.

Вложения

	ТабЖеребьевки.xlsx (11.4 Кб, 15 просмотров)
	ТабПовторов.xlsx (8.5 Кб, 9 просмотров)

0

Ответов по существу нет... И скорее всего не будет. Я теперь сам понимаю, что задача слишком сложная... Только чтобы человеку далекому от темы "въехать" в смысл, уже надо времени уйму потратить.

Попробуем по другому...
Разобьем изначальную задачу на несколько, более простых, а уже потом, поэтапно, попробуем объединить в одну:-)
Уберем "Команды", как очень усложняющее решение условие.
Первое условие, развести на четыре позиции в четырех турах N - участников. Тут все просто - решение имеется от N равном восемь и более. Для начала будем считать, что N всегда кратно четырем, чтобы на данном этапе не заморачиваться со стыковыми боями. Во вложении - простейший пример такой таблички.

Собственно, вопросы:
1. как переставить внутри туров участников, не выходя за рамки каждого тура и только внутри "своей" колонки, чтобы минимизировать повторы участников друг с другом?
2. сколько при N = восьми, может по минимуму остаться повторов?
3. Чему по минимуму должно равняться N (и соответственно, количество боев в туре - N / 4), чтобы развелось вообще без повторов - чтобы каждый участник в одном бою(строке таблицы), пересекся с каждым соперником не более одного раза за все четыре тура ?

Вложения

МинимальныйЭтап.xlsx (9.9 Кб, 11 просмотров)

0