О рассевах

Подготовка масс-старта матчевой 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, каким будет минимальное необходимое количество рассевных точек, необходимых для построения? Кстати, если формулировать задачу математическими терминами, ресь идет о построении ориентированного мультиграфа с заданным числом эйлеровых циклов, но это уже, пожалуй, перебор.

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