четверг, 17 января 2019 г.

Эло рейтинг в ориентировании. Часть 3.

Я, вообще то, планировал уложить все в пару частей, но мысли о том, что еще написать, все появляются. Правда, спамить на гостевой OBelarus я уже перестану. Так что, если еще интересно, следите за обновлениями тут.

Хотелось все формулы и алгоритмы второй части сопроводить примерном из реальной жизни, так что очередной тур BNTU Open прошел как раз вовремя (конечно, можно было привести пример прошлогоднего уже расчитанного соревнования, но это не так свежо и злободневно получится). Для удобства (моего), результаты я сложу в отдельный документ, а дальше сопровожу их своими комментариями.

Рассчет рейтинга

Результаты разделены по вкладкам на мужские и женские, общие и спринтерские. Колонки - имя, рейтинг до старта, изменение рейтинга, рейтинг после старта, суммарный коэфициент до старта (об этом я писал в прошлой части) и место (0 - снят). Тут важно напомнить, что спортсмены с суммарным коэфициентом меньшим или равным 200 считаются новичками. Для новичков, напомню, коэфициент старта удвоен (20 вместо 10 в нашем случае), фактически удваивая величину изменения (в реальности увеличение даже больше, поскольку для новичков другие новички считаются с обычным весом).

Теперь к самим результатам подсчета (они отсортированы по величине изменения рейтинга). В общем рейтинге у мужчин Томашев Олег и Чучва Дмитрий получили максимально возможные для них 20 баллов. Большая группа новичков заработала более 10 баллов, для этого хватило даже 25 места (что не так удивительно, учитывая 77 участников старта). Из спортсменов с устоявшимся рейтингом только Марков Виталий достиг лимита в 10 баллов. Интересно посмотреть глубже, где первое и второе места старта, Стрельцов Василий и Солодкин Сергей, они же наиболее высокорейтинговые спортсмены старта набрали, соответственно всего 2 и 1 балл, что является довольно характерным примеров работы рейтинга. Думаю, введение подобного рода массовых стартов в рейтинг должно иметь очень позитивный эффект. Не сильно влияя на рейтинг лидеров, оно позволит намного быстрее выставить соответствующий действительности рейтинг для остальных, заодно добавив в рейтинг представителей разных возрастов, дав им возможность соревноваться между собой.

Дальше вниз таблицы все достаточно просто: учитывая примерное равенство рейтинга у большинства спортсменов в этой части, изменения примерно соответствуют занятым местам. Я говорил раньше, что в рейтинг иностранные спортсмены включены не были, но это все определялось исключительно протоколами, в результате правило было довольно расплывчатым. Подумав, я решил убрать ограничения - все спортсмены, принимающие участие в старте будут рассчитаны (прошедшие старты я уже вносить по новой в базу не буду, естественно).

У женшин картина несколько иная. Тут можно заметить, что Кунцевич Наталья, заняв четвертое место из 29 участниц, уменьшила свой рейтинг (правда всего на 0.1 балла) - исходя из ее высокого рейтинга, такой результат был ниже ожидаемого. А вот Лебедева Елена, заняв 23-е место, свой рейтинг улучшила. Вторая по рейтингу, Волкова Яна, свой последний старт в качестве новичка (ее суммарный коэфициент на начало старта был равен 200) прошла неудачно и потеряла 20 баллов.

В спринтерском рейтинге картина похожая, но у некоторых спортсменов спринтерский и общий рейтинг различались настолько сильно, что и результаты получились разными. Например Громов Алексей потерял 1 балл в общем рейтинге, но поднялся сразу на 6 баллов в общем. Спринтерский рейтинг Маркова Виталия был значительно выше, соответственно, и прогресс составил не 10, а 6 баллов.

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


четверг, 10 января 2019 г.

Эло рейтинг в ориентировании. А так можно? Часть 2.

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

Для тех, кто остался, я продолжу. Первым в алгоритме подсчета идет определение вероятности победы (или ожидаемого результата) спортсменов исходя из разности их рейтинга. Здесь я использовал наиболее классический подход, где результат спортсмена считается нормально (Гауссово) распределенным относительно среднего уровня (за который принимается текущий уровень). При рейтингах R1 и R2, ожидаемые результаты вычисляются по формулам:
E1 = 1 / (1 + 10^((R2 - R1) / D))
E2 = 1 / (1 + 10^((R1 - R2) / D))
Важным свойством является то, что E1 + E2 = 1 (то есть суммарная вероятность победы обоих спортсменов равняется 100%). D - коэфициент, который и будет определять, как разница в рейтинге соответствует вероятности победы, но важно только его отношение к величинам коэфициентов стартов (о которых дальше). Я принял D = 300. Подставив это значение в формулы, получим, что разница в 100 очков рейтинга соответствует вероятностям 68% / 32%, 200 ~ 82% / 18%, 300 ~ 91% / 9%, 400 ~ 95% / 5%. Наличие физического смысла я считаю одной из приятных мелочей Эло рейтинга, ведь речь идет не только о функциях подсчета, но и о том, что, в конечном итоге, значат сами числа рейтинга спортсменов. Хотя, с практической точки зрения, наличие такой обратной связи может быть не так и велико.

Идем дальше подсчитав ожидаемые результаты E и сравним с ними реальные результаты С (0, 1 или 0.5) получаем некое значение B = С - E. Как я писал в первой части, для каждого спортсмена мы проводим сравнение с каждым из соперников, то есть для каждого спортсмена мы имеем N-1 значений B (где N - число участников старта). Тут возникает вопрос: что с этим всем делать дальше? Вариантов несколько:
  1. Взять среднее значение.
  2. Взять сумму.
  3. Что-то посередине между 1 и 2
Вариант 1 кажется слишком статичным, усреднение может давать для большинства спортсменов слишком маленькие изменение. Вариант 2 - другая крайность, слишком резкие изменения, особенно учитывая существенную вероятность схода (или снятия) даже для топовых спортсменов. Впрочем, это пока мои домыслы, которые я еще буду проверять дальше. А остановился я пока на формуле 
Вt = Sum(B) * log(4, N) / (N - 1)
То есть среднее значение умножается на логарифм количества участников по основанию 4. Четыре означает, что множитель будет равен 3, при числе участников 64, что на данный момент близко к практическому максимуму.

Остается умножить значение Вt на коэфициент значимости старта K и изменение рейтинга готово. Правда перед этим я ограничиваю -1 <= Вt <= 1 и ставлю его -1 или 1 его оно из этих границ вылезает. Это тоже одна из опций, означающая, что модуль изменения рейтинга никогда не может быть больше коэфициента старта. Основная цель - избежать резких падений при сходах высокорейтинговых спортсменов на старте с большим количеством участников. Теперь о коэфициентах стартов, соревнования я разбил на 4 уровня:
  1. K = 40. Мастерские старты и старты WRE.
  2. К = 30. Старты кубка БФО.
  3. К = 20. Чемпионаты и кубки областей, старты на соревнованиях с этапами кубка БФО.
  4. К = 10. Все остальное
Пункт 4, в моем понимании, еще одно преимущество такого рейтинга. Здесь нет необходимости выделять группу расчитываемых стартов, устанавливать лимит на количество зачетных стартов. Тот факт, что рейтинг изменяется в обе стороны, не дает очевидных преимуществ спортсменам бегающим больше (или меньше) стартов (хотя о некоторых возможных минусах - дальше).

Для подсчета рейтинга я собрал старты последних 5 лет, элитные группы у мужчин и женщин. В теории можно пойти дальше и расчитывать в один рейтинг все участвующие группы, но есть опасение, что пересечений между участниками разных групп будет слишком мало для стабилизации рейтинга и возможности достоверно отображать, например, разницу в уровне М16 и М60. Женские и мужские рейтинги, естественно, сичтаются отдельно и соотношение чисел между ними не говорит ни о чем. Источником служили протоколы на OBelarus.net и Orient.by, за исключением массовых открытых стартов вроде ЗС было посчитано практически все (хотя и ЗС не является каким-то ограничением, скорее экономией времени, при внесении текущего рейтинга я планирую учитывать все старты по максимуму, так в последнюю версию уже попали туры BNTU Open). Из расчета исключались спортсмены с пометкой в/к и иностранные спортсмены, хотя в отношении некоторых спортсменов мнения протоколов о гражданстве не сходились (Ласкаржевский Владислав - самый яркий пример), тут, в целях экономии времени, я просто доверял протоколам. Всего вышло около 540 стартов (считая отдельно мужчин и женщин). Начальный рейтинг каждого спортсмена устанавливается в 1500.

Само написание подсчет рейтинга уместилось в 15 минут работы и 20 строчек кода, что идет в слабое сравнение со всей подготовительной работой. Осталось нажать кнопку и получить примерно следующее (в списке присутствуют спортсмены, пробежавшие за последний год стартов с суммарным коэфициентом не менее 60, поля таблицы после рейтинга: старты за год, прогресс за год и суммарный коэфициент за год):




Пожалуй, вышло что-то похожее на правду. Что еще мне хотелось добавить - это часто используемые в рейтингах Эло особые правила для новичков. В нашем случае они будут выглядеть так:
  1. Для спортсмена новичка все коэфициенты К удвоены.
  2. Для спортсмена неновичка, при сравнении с новичком при расчете рейтинга, результат сравнения учитывается с весом 0.5 при расчете среднего значения (соответственно и в формуле Вt = Sum(B) * log(4, N) / (N - 1), N - это взвешенное количество участников).
Остается еще решить, кого считать новичком. Учитывая разные коэфициенты стартов, простое количество будет работать не слишком хорошо. Я ввел подсчет суммы коэфициентов стартов, спортсмен, у которого эта сумма <= 200 - новичок (с точки зрения системы его рейтинг вызывает меньше доверия и его нужно побыстрее привести к нужным значениям).

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

Впрочем, чем долго рассуждать и угадывать, проще взять и проверить:


Рейтинг растянулся, при этом не пережив слишком существенных изменений - это достаточно позитивно. Тут мне захотелось проверить, насколько время начала рейтинга влияет на его значение сейчас, и я добавил еще 2 года стартов, на этот раз ограничившись стартами кубка БФО. Результат (полные таблицы ниже) - не слишком-то влияет, просто рейтинг еще слегка растянулся. В целом - это то что от рейтинга и ожидалось - давние результаты должны быть практически незаметны сейчас, но тут получить ожидаемый результат приятно.

Осталось добавить расчет отдельно спринтов (в эту категорию включены и удлинненые городские, и лесные спринты) и всего остального. Такой рейтинг может быть даже более показательным, но из-за меньшего количество стартов смотреть на него нужно пока осторожней. База спортсменов была по возможности подчищена, но если вы найдете там какие -то ошибки, например неучтенные девичьи фамилии, как два разных человека (парсер результатов про такие вещи не в курсе, я тоже не всегда) - сообщайте. В этих списках - все спортсмены, но при отображении в дальнейшем, по определенному весу стартов за последний год, неактивные спортсмены будут исключатся.


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




понедельник, 7 января 2019 г.

Эло рейтинг в ориентировании. А так можно? Часть 1.

Перед тем как отвечать на вопрос заголовка, стоит вкратце рассказать об Эло рейтинге. Эло рейтинг был разработан Арпадом Эло для подсчета рейтинга шахматистов в середине XX века, вскоре он стал официальным рейтингов международной шахматной федерации. В настоящий момент рейтинг Эло является официальным и в других, подобных шахматам, видах спорта, а неофициально подсчет ведется уже практически для любого вида спорта с матчами 1 на 1 (включая и командные). Вот, например, футбол или теннис. В футболе, кстати, и официальный рейтинг ФИФА недавно перешел на такую систему. При этом, говоря о рейтинге Эло, я имею в виду именно общие принципы подсчета, в каждом конкретном случае сами формулы подсчета могут отличатся.

Теперь, собственно, об этих принципах (пока по-прежнему о матчах 1 на 1).

Основной: рейтинг соперников на начало матча и результат матча определяют новый рейтинг соперников; рейтинг - это всегда просто одно число, он не хранит истории и не считается ни за какой конкретный период; рейтинг - показатель силы спорстмена на данный момент времени. Можно сравнить это с циклической системой (например в теннисе), где рейтинг - это сумма очков за последний год, по достижении года эти очки из рейтинга сгорают.

Можно выделить плюсы и минусы систем (хотя правильней будет назвать это разными областями применения). Если вы хотите награждать спротсменов по итогам рейтинга, тогда циклическая система вам подойдет - значение рейтинга на конец года просто даст вам сумму результатов спортсменов за год. В системе Эло это не сработает, поскольку там нет конкретного интервала времени, а веса стартов просто плавно убывают (это, наверное, при желании можно выразить математически). Рейтинг на конец года - это в большей мере старты ноября, в меньшей мере - старты апреля, да и даже старты пятилетней давности тоже вносят какой-то вклад, пусть и небольшой. С другой стороны, свойство большей важности последних стартов как раз и является преимуществом системы Эло при определении силы спортсменов в данный конкретный момент времени.

Еще один принцип Эло заключается в механизме подсчета нового рейтинга на основе изначальных рейтингов и результата. Попробую объяснить это не слишком загружая математикой. Определяющим являются не сами рейтинги спортсменов, а их разница. Предположим встречаются спортсмены с рейтингами R1 = 1400 и R2 = 1600. Рейтинг Эло исходя из своей формулы определяет вероятности победы каждого из спортсменов (тут уже подключается теория вероятностей, скажу только что существует несколько разных используемых вариантов определения вероятности). Пусть, для примера, в нашем рейтинге разница в 200 очков соответствует вероятности победы 25% на 75%. Соответственно, ожидаемый результат E1 = 0.25, E2 = 0.75. Дальше смотрим на реальный результат C: победа = 1, поражение = 0, ничья = 0.5. Допустим, спортсмен 1, несмотря на разницу в рейтинге, добился победы. Изменение рейтинга - разность между реальным и ожидаемым результатом. B1 = C1 - E1 = 1 - 0.25 = 0.75. У проигравшего спортсмена, соответственно, B2 = C2 - E2 = 0 - 0.75 = -0.75. Остается умножить результат на коэфициент старта K, обычно они различаются для стартов разного уровня - это уже правила каждого конкретного рейтинга. Пусть, в нашем случае K = 30. Тогда в результате R1 = 1400 + 0.75 * 30 = 1422.5, R2 = 1577.5

Теперь можно вернуться к ориентированию. Эло хорошо работает для матчей 1 на 1, но как переложить его на соревнования с несколькими спортсменами? Тут будет работать следующий принцип: для каждого спортсмена результат разбивается на отдельные матчи против всех остальных участников (то есть на старте с 30 участниками таких матчей у каждого будет 29). Изменение рейтинга считается по принципу, описанному выше, дальше останется только определить, как скомбинировать эти отдельные результаты в общий итог старта для спортсмена. Вариантами могут быть: среднее значение, сумма изменений либо какая-то более сложная формула. Об этом я напишу уже во второй части. Пока же нужно собрать в базу результаты соревнований последних лет - это более трудоемкая задача. Имея базу, можно будет экспериментировать.

Несколько картинок, для привлечения внимания:

А подробнее о результатах экспериментов - уже во второй части.

вторник, 12 декабря 2017 г.

О стартовых взносах

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

Итак, задача: найти оптимальный стартовый взнос для соревнований.
И сразу, чтобы внести ясность - здесь и далее "оптимальный" = "дающий максимальную прибыль". Тыкать пальцем в небо не стану, а применю математику. Для этого нужно построить примерную математическую модель (при этом "примерную" - это может быть даже слишком мягкое слово, модель будет очень примерной - такими же будут и результаты, но об этом я уже предупреждал).

Построение математической модели начну с расходов. Пусть расходы делятся на две категории:
1) Общие расходы, не зависящие от количества участников (работа судей, организация центра соревнований, аренда спорткомлекса/парковки, расходные материалы). Обозначим их "C".
2) Расходы на одного участника (печать/покупка карты, аренда отметки). Обозначим как "a".

От расходов сразу перехожу к доходам. Поскольку искомое значение - это размер стартового взноса, его я и обозначу как "x". Имея конкретные условия старта (время, место, карта, реклама, призы и т.д.), меняем только стартовый взнос. Количество участников в фиксированыых условиях, соответственно, будет функцией от стартового взноса - пока просто обозначаю как "f(x)".
Теперь есть все, чтобы найти суммарный доход от соревнований "P" - количество участников, умноженное на доход от одно участника (стартовый взнос минус затраты на участника), минус общий расход. Если проще, то:
P = f(x) * (x - a) - C

Наша задача - найти х, при котором P максимально (кстати говоря, при этом оно не обязательно положительно - это жестокое жизненное уточнение). Задача, если не ошибаюсь, из школьной программы 10-го или 11-го класса. Для поиска локального максимума (и минимума) нужно найти корни производной. Поехали:
P' = (f(x) * (x - a))' - C' = f'(x) * (x - a) + f(x) * (x - a)' - 0 = f'(x) * (x - a) + f(x)
f'(x) * (x - a) + f(x) = 0

На этом у меня всё.
Шутка.
Ну то есть дальше остается только сделать шаг, который сделает математическую модель "сферическими соревнованиями в вакууме". Ну и ладно.
f(x) - влияние стартового взноса на количество участников. Что, вообще, можно предположить про эту функцию.
1) Она монотонно убывающая. Было бы довольно странно, если бы количество участников росло, при увеличении стартового взноса (хотя с коллективным сознанием чего только не случается).
2) Имея свой максимум при нулевом стартовом взносе (в отрицательный стартовый взнос я не полезу) она сначала уменьшается довольно медленно (стартовый взнос в 1-2 рубля мало кого испугает).
3) Достигнув некоего значения (пусть будет "P1") стартовый взнос уже начинает оказывать существенное влияние на посещаемость, отток увеличивается.
4) Достигнув значения "P2" мы потеряли почти всех участников. Оставшиеся утекают медленнее, но рано или поздно f(x) все таки достигнет нуля. Впрочем, эта часть функции нас уже интересует меньше.

Естественно, для анализа функции ее нужно сделать непрерывной, так что с нецелым числом копеек и участников придется смириться. Кстати, еще одним упрощением модели является одинаковый стартовый взнос для всех участников, иначе считать все пришлось бы для каждой группы отдельно.
Набросаю такие условия:
1) При стартовом взносе 0 рублей наш старт посетит 250 человек.
2) При взносе в 5 рублей 10 человек откололось, осталось 240 человек.
3) Взнос в 25 рублей оставил нас с 10-ю отчаяными фанатами.
4) При 30 рублях участников не осталось.

Дальше воспользуюсь онлайн приложением (https://tools.timodenk.com/cubic-spline-interpolation) и проинтерполирую. Получаю такой график.

Сложно сказать, насколько он похож на правду, но выглядит неплохо.
Запись функции выглядит не так красиво:

Возвращаясь к выражению
f'(x) * (x - a) + f(x) = 0
посчитать его нужно будет для каждой из трех функций отдельно и найти корни, попадающие в соответствующий отрезок. Перед этим, нужно еще установить значение для "a" - расхода на одного участника. Пусть будет 3 рубля для начала, потом с этим можно будет поиграться.
Всю грязную работу я тут показывать не буду, в конце концов результатом будет кубическое уравнение. Его, конечно, я тоже не буду решать сам, для этого использую https://www.symbolab.com/solver/polynomial-equation-calculator/

Ну а результатом всего этого математического безобразия станет число x ~ 13.43 рубля. Количество участников f(x) ~ 148 человек.
Поиграемся значением расходов. При той же функции f(x) установим a = 0 рублей (не очень жизненно). x ~ 12,14, f(x) ~ 166.
a = 6 рублей. x ~ 14.87 рублей, f(x) ~ 127 человек.
В общем, это довольно интуитивно, увеличение затрат на человека двигает оптимальный стартовый взнос вверх (в данном случае примерно в 2 раза медленней самого взноса).

Так получилось, что начал я сразу с более сложной модели, но можно попробовать упростить её вот так:
Проще - не значит хуже, возможно завсимость участников от стартового взноса ближе к линейной. Расчет с похожими входными данными:
f(x) = 250 - 250 * x / 30
Тут уже не нужны сторонние приложения, несколько подсчетов, и получаем:
x = (30 + a) / 2
То есть, в этой модели оптимальное x больше (а f(x), соответственно меньше).
При а = 3, x = 17.5 - дополнительных 4 рубля. f(x) = 125 - минус 23 человека.
С такой зависимостью, кстати, оптимальный стартовый взнос достигается при числе участников меньше половины от максимально возможного.
Тогда хочется верить, что f(x) в реальной жизни всё же ближе к первому варианту. 

Какая она на самом деле? Да кто ж его знает.

вторник, 31 октября 2017 г.

О рассевах

Подготовка масс-старта матчевой 2017 разбудила во мне математика и заставила чуть глубже взглянуть на известный вопрос рассеивания. Чтобы не потерять свои мысли просто так, я постараюсь их тут систематизировать.

Начну с азов: рассев "бабочка". Для экономия места дальше я везде буду использовать правый вариант (линия со стрелками может обозначать линейный участок дистанции любой длины), опуская все нерассевные КП, не представляющие интереса.

Все читающие это сразу скажут, что число рассевов, которые дает такой элемент - 2.
Можно чуть усложнить задачу, добавив бабочке еще одну петлю.
Исходя из опыта или быстрого подсчета, большинство легко ответят, что число рассевов здесь равно 6. На всякий случай, все возможные порядки прохождения: 123, 132, 213, 231, 312, 321.
В общем случае, для бабочки из n петель число рассевов (пусть оно дальше обозначается как R) равно n! = n*(n-1)* ... *3*2*1
То есть для 4-х петель R=24, для 5 - R=120. Это уже явно покрывает потребности любого старта, но пятикратное посещение одного пункта может вызвать ощутимое отторжение у спортсменов. На практике такой рассев можно реализовать с центром на старте/финише, заодно организовав там подпитку и смену карт. На ум приходит марафон в Багуте 2013, матчевая 2004 в Боровой, если покопаться в памяти хорошо, таких стартов можно будет вспомнить довольно много.

Идем дальше. Ф-рассев, "карусельска", "лепесток", то ли я забыл, то ли никогда не знал его правильного названия.
Тут тоже все понятно - 2 варианта рассева, рассев такого плана используется сейчас повсеместно и, похоже, бесповоротно вытеснил "бабочку". Наверное, основной причиной является то, насколько органичней можно вписать "лепесток" в дистанцию, а при наличии смены карт еще и скрыть рассев от участников.
Хотя встретить такой рассев можно много где, всегда используется только самая простая его вариация - 2 пути вперед, 1 - назад. В общем случае, рассев может выглядеть как 2 пункта, с n вариантами пути вперед, n-1 - назад. В таком случае, R=n!*(n-1)! - то есть много (для n=3, R=12; n=4, R=144). Проблемы те же, что и в "бабочках" с большим количеством лепестков. На практике, решить их можно также, сделав одну из точек стартом/финишем, а вторую - подпиткой.
По крайней мере, такая дистанция не выглядит безнадежной.

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

Пока, все приведенные рассевы давали в результаты четное число вариантов. Вопрос, который возник у меня какое-то время назад: "Может ли число рассевов R, быть нечетным числом >2?"
Желающие, могут подумать, к этому вопросу я вернусь позже.

Пока рассмотрю еще один базовый тип рассеивания. Эстафету обычную или эстафету одного участника концептуально можно нарисовать так:
k - число участников эстафеты (либо количество кругов one-man-relay), n - количество рассевных элементов.
R=(k!)^n - довольно внушительное число. Если переводить в реальную жизнь, то для трехэтапной эстафеты, с 3 рассеиваниями R=(3!)^3=6^3=216. Количество различных неповторяющихся этапов меньше - это просто k^n, то есть 3^3=27.

Говоря про эстафеты, хочется поднять одну идею, навеянную эстафетой WOC2015 в Шотландии.
https://www.woc2015.org/images/Relay_All_Courses_map.png
Обратите внимание на схемы дистанций справа - они содержат не только стандартные тройные рассевы, но и неожиданные шестерные. На каждом этапе участники дважды проходят путь между КП 67 и 47. В теории это может дать R=6!=720 различных рассеиваний за счет только одного этого элемента. На практике, рассевы были сгруппированы попарно (иначе один участник мог бы получить 2 слишком похожих варианта, например 67-59-47 и 67-76-60-47). Таким образом R=6*4*2=48, что все равно больше двух последовательно соединенных тройных рассевов (R=36). Однако главным преимуществом является то, что паровоз может быть разбит сразу на 6 потоков, вместо обычных трех.
Идею можно продолжить, например, группировать варианты можно не попарно, а группами по 3, скажем ABC и DEF. Если варианты внутри групп близки между собой, нашим желанием будет сделать такие рассевы, при котором каждый участник проходит на своем этапе по одному варианту из каждой группы. Тогда R=6*3*4*2*2*1=288 (если вы нашли ошибку в этом вычисление - сообщайте). На самом деле, такое рассеивание может убить сразу двух зайцев: увеличить количество вариантов и провести участников по одной местности без заметных повторений (например, такой рассев можно применить на 1-ый КП, а потом сразу после зрительного КП).
Вот как этот элемент будет выглядеть схематично:

Вернусь к эстафете одного участника. Чаще всего, из практических соображений, такие старты проходят в 2 круга. Число рассеиваний в результате заметно уменьшается, но упрощается планировка и организация.
Говоря об one-man-relay обычно подразумевают рассев охватывающий всю дистанцию от старта до финиша, то есть такой формат:
На самом деле, это не всегда так, присмотритесь к такой дистанции: http://omaps.obelarus.net/show_map.php?user=romanb&map=523
Схема рассеивания выглядит хаотичной и сразу получила определение "паутинка".
Если присмотрется к рассевам от 1-го до 10-го КП и от 15-го до 27-го КП, формализовать их и исключить петлю у 22-го КП, в узких кругах известную как "березинская бабочка", не дающую рассева, получим такую схему дистанции.
Так можно увидеть два независимых рассева типа one-man-relay с двумя элементами рассеивания каждый. R=(2^2)*(2^2)=16

Пока количество рассевов можно было определить аналитически, но будет ли это так для любой дистанции. Перехожу к заключительной части анализа, разбору рассевов на матчевой 2017.
Предупреждение: эта чать может быть еще тяжелее для понимания, чем первая.
http://3drerun.worldofo.com/?id=-457865&type=info
Вообще говоря, какого-то конкретного рассева заранее не планировалось. One-man-relay предъявляет требования к хорошему старту/финишу и местности вокруг него (поскольку там нужно провести спортсменов как-минимум два раза), так что он был отброшен. "Паутинка" предоставляет больше свободы в выборе места рассеивания, ее минусом (с которым пришлось смириться), является перенасыщение карты линиями, сбивающими спортсменов.
Дистанции, в целом, планировалась без оглядки на рассевы, просто в местах, где точки можно было использовать несколько раз - это делалось. Только в редких случаях перегон делался для закольцовывания рассева (пожалуй только 36-40 для Д1). После этого оставалось посчитать, что же вышло в итоге, вот к этому я и перехожу.
Группа Д3 получила довольно простой рассев типа "лепесток" внутри "бабочки" с четырьмя вариантами. У Д2 и Д1 все было несколько сложнее. Дистанция Д2:
Для начала нужно упростить эту схему, оставив только рассевные КП (посещаемые несколько раз) и соединить их, если между ними существует участок дистанции.
Можно указать несколько способов упрощения.
1) Предположим, что мы вставляем петлю "бабочки" (как на КП 44) в любое место существующей дистанции. Если в точку вставки петли спортсмен прибегает дважды, то каждому варианту рассева изначальной дистанции можно поставить два варианта дистанции с "бабочкой" (с уходом на нее при первом посещении или при втором). В общем случае, петля увеличивает количество вариантов во столько раз, сколько раз точка посещается спортсменом (без учета самой бабочки).
Так "бабочку" можно довольно эффективно использовать не как самостоятельный, а как вспомогательный элемент рассеивания. Слегка изменю уже приведенный здесь рассев (слева), соединив вместе два элемента:
Для дистанции слева R=4, справа - R=2*2*3=12
Возвращаясь к схеме дистанции Д2, я запоминаю множитель 2 и дальше рассматриваю такую схему:
Следующее упрощение которое можно сделать:
2) Оба пути, выходящие из КП 47, ведут к КП 44. Есть два варианта, как поставить им в соответствие пути исходящие из КП 44 (в общем случае, для n путей - это будет число n!). Поскольку оба пути 47-44 симметричны, полученые уменьшенные дистанции будут одинаковые. Число рассевов уменьшенной дистанции можно будет просто умножить на два (то есть запоминаемые множитель теперь равен 4). В результате упрощения, КП 44 перестает быть рассевным.
Немного "причесав" схему, можно увидеть что-то очень похожее на one-man-relay элемент, только направление путей движения будет отличатся.
Видимых способов упрощения я больше не вижу. Не уверен, что многие сходу уверенно назовут число R такой дистанции (хотя 4, из-за сходства с дистанцией one-man-relay напрашивается). Благо, посчитать его несложно.
Применить можно алгоритм поиска в глубину в графе (если вы слышали слово рекурсия, но не уверены что оно значит - то вот классический случай применения рекурсии). Вкратце алгоритм будет выглядеть так:
1) Берем первый рассевный КП (50), по очереди смотрим все выходящие из него пути (50-56, 50-47).
2) Для каждого пути предполагаем, что рассев начинается с него. В результате можно получить упрощенную схему дистанции. Если полученная схема уже известна и рассчитана (например дистанция распалась в линейную, с R=1), то останавливаемся, иначе рассчитываем R этим же алгоритмом (то опять с пункта 1).
3) Суммируем результаты, полученные для каждого пути, получаем R для изначальной дистанции.

Поехали. Если начать рассев с пути 50-56, то оставшаяся дистанция будет выглядеть так (КП 50 становится обычным линейным, и из схемы его можно убрать):
Дальше рассчитывать не обязательно - это классический "лепесток" с R=2.
Смотрим 50-47:
Двойная "березинская бабочка" - это красиво, но рассеиванию не помогает. По очереди убирая петли (и добавляя множитель 1), получим R=1.
Возвращаясь к исходной схеме дистанции, суммируем результаты для обоих путей, получаем R=3. Если вы еще помните вопрос о нечетных R, то вот ответ на него. Пожалуй, назову этот рассев "божьей коровкой".
Прямо скажем, эффективностью он не отличается, спортивная справедливость тоже прихрамывает (паровоз участников делится не равномерно и не одновременно), но уж такой он есть. Вообще-то, отдельные преимущества над схожим рассевом типа one-man-relay у него можно найти, но не с математической точки зрения, а с точки зрения планирования дистанции и разнообразия путей.
Осталось вернутся к исходной дистанции Д2. Множитель был равен 4, а значит R=4*3=12 вариантов рассева.

Для закрепление, вкратце тот же алгоритм для Д1
Формализация:
Убираем петлю:
Если полученную дистанцию обозначить Д1а, то R(Д1)=2*R(Д1а). Это все, чего можно добится симметричными упрощениями. Если продолжать вводить термины, то "паутинкой" я бы называл именно такие рассевы, неупрощаемые до линейных дистанций преобразованиями, которые я приводил выше. Но это уже малополезная информация для, собственно, ориентирования.
Фиксируем первым путем 51-46. Д1б:
КП 51 и 60 больше не являются рассевными, удаляя их получаем "божью коровку". R(Д1б)=3.
Возвращаясь назад фиксируем 51-60. Д1в:
Поскольку 51 больше не рассевный, в дистанции появилось 2 симметричных пути 60-46, один направляем к КП 36, второй к КП 40. Д1г:
Очередной выход "божьей коровки". R(Д1г)=3. Остается сложить всю формулу назад.
R(Д1)=2*R(Д1а), R(Д1а)=R(Д1б)+R(Д1в), R(Д1в)=2*R(Д1г), подставляя R(Д1б)=R(Д1г)=3: R(Д1)=2*(3+2*3)=2*9=18.

На волне математики и закончу (большинство все равно не дочитает до этого момента). На вопрос о нечетных R ответ нашелся, нетрудно показать алгоритм построения рассева с любым заданным R:
для такого рассева R=n+1. Остается вопрос оптимального, с точки зрения минимизации количества рассевных точек.
В общем виде сформулирую вопрос так: для заданного R, каким будет минимальное необходимое количество рассевных точек, необходимых для построения? Кстати, если формулировать задачу математическими терминами, ресь идет о построении ориентированного мультиграфа с заданным числом эйлеровых циклов, но это уже, пожалуй, перебор.

На этом пора закончивать.

понедельник, 24 марта 2014 г.

Ливье. 22.03.2014

Приятная тренировка, немного разведка местности. Карта, на удивление, хороша - лес и дороги чистые, рельефа мало, может чуть больше чем в соседнем Асино. Между картами чуть больше километра, и сходство ощущается.
По дистанции серьезно натупил на 3-ем пункте, но понял ошибку довольно быстро. Неправильно оценил новые контура на 6-ом и промахнулся на 16-ом, а в остальном неплохо.