[ОТВЕТИТЬ]
Опции темы
26.08.2015 11:13  
MWWRuza
Предыстория... Есть написанная мной некая программка, предназначенная для автоматизации стартов в авиамодельном спорте, в классе RCCR - вот здесь я описывал, что это такое. Одним из основных модулей этого "АРМ секретаря стартов" является жеребьевка. Остальные функции - занесение и подсчет результатов, расчет рейтингов этапа, пилотов, подсчет личных и командных мест, работают нормально и вопросов не вызывают. А вот с жеребьевкой есть проблемы... При чем. проблемы стали усугубляться в этом году - в связи с кризисом, количество участников существенно сократилось, и все "косяки" полезли наружу...

Краткое описание ТЗ:

1. Жеребьится четыре тура.
2. В каждом бою участвуют 4 пилота.
3. Каждый тур состоит из N-количества боев, равным общему количеству участников/4
4. При некратном 4 количестве участников, производится "стыковка" туров с помощью стыковых боев. Например: при количестве участников 25, проводятся три тура по 6 боев, и один, четвертый тур 7 боев - в него собираются остатки от деления на 4, в результате все равно каждый участник отлетвает 4 боя, просто в одном из трех он не летит, а в четвертом летит дважды. В остальных случаях, когда остаток от деления 2 или 3, тоже все стыкуется по аналогичному принципу.

А вот теперь самое интересное, критерии жеребьевки:

5. Каждый пилот должен по одному разу слетать на одном цвете ленты(стартовой позиции). Условие обязательное и неотключаемое.
6. По возможности надо развести членов команд, что-бы они друг с другом не встречались в одном бою. Это не всегда возможно - например, теже 25 участников, а в одной из команд оказалось 7 пилотов... В первых трех турах, по 6 боев, они все равно будут пересекаться, и только в четвертом, где семь боев, можно их развести.
7. По возможности надо развести пилотов от повторов, что-бы уменьшить вероятность дважды а то и трижды встретиться одним и тем-же пилотам в разных турах.

Вобщем, все это сейчас реализовано и работает. Но!!! Писал я это тогда, когда этапы проводились по 40 человек, команд было много тоже, и все это довольно сносно работало, в архиве программка вместе с базой данных с самого начала, можно посмотреть у кого есть возможность(это конфигурация под 1С 7.7 любой компоненты).

Алгоритм сейчас устроен линейно -
1. Жеребьится первый тур, используя генератор случайных чисел, из критериев только разводятся команды.
2. Жеребьится второй и последующие туры, но добавляются критерий цвета ленты и повтора - для этого анализируются предыдущие туры.

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

Есть мысль, переделать весь алгоритм: жеребьить сразу в одной таблице все четыре тура, добиваясь минимальных пересечений по критериям, а потом делить по отдельным четырем турам, с учетом стыковых боев... Вобщем, высшая математика получается, вместе с теорией матриц...

Вот такая нетривиальная задача... С удовольствием принимаю все советы, кроме - "брось ты это нафиг, зачем тебе это нужно?".

PS Написано это все на 1С 7.7, но, это не принципиально - на чем мне было проще, на том и реализовывал. Для любой среды разработки, алгоритм будет в принципе один...

PSS Проект не коммерческий, делаю на чистом энтузиазме, по принципу - "если не я, то кто?"
 
28.08.2015 14:11  
MWWRuza
Две ночи работы, и в результате что-то начинает проясняться, но только начинает...
Вобщем, "чем дальше в лес, тем толще партизаны!"...
Не буду грузить кодом программы, там все запутано, а разбираться в чужом коде, ясное дело, никто просто так не станет... Вот результат работы в Exel-евском файле, сейчас в таблице разведены пилоты по четырем турам, с учетом условия - "по одному разу на каждой позиции(цвете ленты)", с учетом "стыковых" боев(отделено жирной черной линией, первые три тура по 6 боев, 4-тый 7 боев), максимально разведены пересечения команд - их всего три, потому, что в одной команде 7 пилотов, а количество боев в трех турах по 6, по этому по другому не получится.

Осталось самое сложное - теперь надо минимизировать повторы(это когда один пилот летает с конкретным соперником в течении всех соревнований более одного раза)... Сейчас их довольно много, при чем, некоторые повторяются более двух раз... Например, пилот Костенко Иван, во всех четырех турах встречается в одном бою с пилотом Сысоевым Сергеем...
Двигать пилотов можно только в пределах одного столбца таблицы, и в пределах строк принадлежащих одному туру, при этом учитывая не пересечение со своими членами команд...

Каким образом это сделать, ума не приложу... В голову лезут только какие-то бесконечные циклы с ограничением по количеству попыток и с запоминанием лучших результатов, с последующим возвратом к наилучшей запомненой комбинации... Но, чувствую, что это совсем не оптимально, должен быть более простой и эффективный алгоритм... Но, как его придумать??? Прям задачка для любителей головоломок
 
28.08.2015 14:26  
MWWRuza
Перезалил файл, потому, что попытался загрузить в хранилище исходный xls, а форум автоматом заархивировал его в 7zip, после чего он оказался нечитаем... Вобщем, заархивировал сам в rar, и перезалил. Теперь, читается: Жеребьевка
 
28.08.2015 17:34  
OlegON
Цитата:
Сообщение от MWWRuza
Перезалил файл, потому, что попытался загрузить в хранилище исходный xls, а форум автоматом заархивировал его в 7zip, после чего он оказался нечитаем... Вобщем, заархивировал сам в rar, и перезалил. Теперь, читается: Жеребьевка
Код:
diff -s Жеребьевка из rar.xls Жеребьевка из 7z.xls 
Files Жеребьевка из rar.xls and Жеребьевка из 7z.xls are identical
 
28.08.2015 18:06  
MWWRuza
Ну, значит у меня на компе 7zip криво разархивируется, тем-же WinRar... А родного для него WinZip у меня на компе нет, точнее есть, но с истекшим сроком бесплатного использования, не работает. Все архивы в принципе WinRar открывает нормально, поэтому как-бы и ненужен был, первый раз подобный косяк встретился... Да и фиг с ним, щас голова другим забита, "супер-интеллектуальный" алгоритм изобретаю по сабжевой задаче.
 
28.08.2015 19:22  
OlegON
Извини, но , выкинь винрар, как давно уже пора было сделать, особо в свете моего сомнения, что ты его купил :)
Что касается сути вопроса, то основная сложность в том, что когда ты все понятно опишешь, то сам поймешь, что нужно сделать :) Поэтому тут никого нет, что понять суть соревнований и ранжирования сейчас, я пока, например, особо не могу.
Если представить себе соревнования и пересечения соперников в виде дерева, то, видимо, берешь рекурсию и идешь вверх по дереву, наращивая массив соперников. Оценивая ситуацию, берешь количество совпадений с имеющимся массивом пройденных соперников и берешь вариант наименьшего совпадения по количеству.
 
"Спасибо" OlegON от:
28.08.2015 20:09  
MWWRuza
Да это понятно, что суть соревнований мне понятна, как никому другому... И объяснить ее "на пальцах" довольно сложно.
Но, в принципе, можно абстрагироваться от соревнований, и просто видеть таблицы - ту, что из предыдущего сообщения, и эту, дополнение к ней, содержащую список повторов...
А дерево... Я как-то слабо себе представляю, как эти таблицы представить в виде дерева... Там все прямое, никакого ветвления нет, есть четыре колонки, и четыре диапазона строк, внутри которых можно двигать значения, чтобы добиться наименьших повторений комбинаций в строках...
 
28.08.2015 21:26  
OlegON
я подразумевал, что соревнование строится аналогично такой схеме, нет?
 
28.08.2015 22:05  
twix
Енто ж финальная таблица. А сперва участники должны быть разбиты на группы, в которых играют друг с другом не менее одного раза. По итогам этих отборочных игр участник, набравший бОльшее количество очков попадает в приведённую тобой табличку.

ЗЫЖ Имхо всё, что приведено выше, ибо я не спец... просто немного логику применил.
 
28.08.2015 22:08  
OlegON
Хм, я думал, что просто определяется именно жеребьевкой чуть длиннее дерево (схемку просто в инете первой выцепил).
 
 


Опции темы



Часовой пояс GMT +3, время: 22:50.

Все в прочитанное - Календарь - RSS - - Карта - Вверх 👫 Яндекс.Метрика
Форум сделан на основе vBulletin®
Copyright ©2000 - 2016, Jelsoft Enterprises Ltd. Перевод: zCarot и OlegON
В случае заимствования информации гипертекстовая индексируемая ссылка на Форум обязательна.