В этом разделе излагаются правила определения последовательности, в которой должны быть опробованы перестановки, обмены и обмены спущенных игроков, чтобы создавать варианты спаривания в правильном порядке. Общий основной принцип, как всегда, заключается в “минимальном возмущении” спаривания. Это означает, что всегда надо перемещать того игрока (или тех игроков), чьё перемещение вызовет наименьшее возможное отличие спаривания от “естественного”, обеспечивая в то же время наилучшее качество самого спаривания. Чтобы избежать недоразумений, следует иметь в виду, что любое изменение порядка в подгруппе S2 (перестановка) по определению предпочтительнее даже единичного обмена между подгруппами S1 и S2.
Перед любой перестановкой или обменом все игроки в группе должны быть помечены последовательными порядковыми номерами в группе (сокращенно ПНГ), представляющими их соответствующий порядок ранжирования (согласно Статье A.2) в группе (т.е., 1, 2, 3, 4,...).
| Использование парных идентификаторов на этом этапе может иногда приводить к путанице. Поэтому даём временные порядковые номера игрокам, как очень удобное средство для упрощения применения правил ниже. |
D.1 Перестановки в подгруппе S2
Перестановка это изменение порядка ПНГ (представляющих всех игроков-резидентов) в подгруппе S2.
Все возможные перестановки сортируются в зависимости от лексикографического значения их первого N1 ПНГ, где N1 - количество ПНГ в подгруппе S1 [в этом контексте остальные ПНГ подгруппы S2 игнорируются, потому что они представляют игроков, которые должны составлять остаток в случае неоднородной группы; или должны спускаться в случае однородной группы - например, в однородной группе из 11 игроков это 6-7-8-9-10, 6-7-8-9-11, 6-7-8-10-11,..., 6-11-10-9-8, 7-6-8-9-10,..., 11-10-9-8-7 (720 перестановок); если группа неоднородная с двумя спущенными игроками, то это: 3-4, 3-5, 3-6,..., 3-11, 4-3, 4-5,..., 11-10 (72 перестановки)].
| Все перестановки сортируются или сравниваются на основе словарного (“лексикографического”) порядка, так что одна данная перестановка предшествует или следует за другой, если строка, образованная игроками ПНГ первой перестановки, предшествует или следует за строкой второй. Метод сравнения строк - тот же, что уже показан при сравнении РО*. Подгруппа S1 может иметь или не иметь такое же количество игроков, как подгруппа S2. Чтобы сравнение имело смысл, необходимо определить количество сравниваемых элементов каждой из двух строк ПНГ. Для каждого элемента в подгруппе S1 (каждый из которых, конечно, представляет игрока) надо найти сопоставление. Поэтому подсчитываем количество N1 элементов в подгруппе S1, тогда как остальные игроки (на данный момент) не имеют значения. Простой пример поможет прояснить ситуацию: рассмотрим однородную группу {S1=[1];S2=[2,3,4]}. Все возможные перестановки в подгруппе S2 (правильно отсортированной и включающей начальную подгруппу S2): [2,3,4]; [2,4,3]; [3,2,4]; [3,4,2]; [4,2,3]; [4,3,2]**. Так как надо спарить №1 с первым элементом из подгруппы S2, с первого взгляда очевидно, что [2,3,4] и [2,4,3] имеют один и тот же эффект***; и то же самое сохраняется для [3,2,4] и [3,4,2]; и для [4,2,3] и [4,3,2]. Поэтому фактическая последовательность перестановок выглядит следующим образом (элементы в фигурных скобках "{...}" не имеют значения и на этом этапе игнорируются): [2]{3, 4}; [3]{2, 4}; [4]{2, 3} * Подробнее см. комментарий к Статье C.6. Обратите внимание, что использование букв алфавита будет полностью эквивалентно цифрам, по крайней мере, для групп с менее чем 26 игроков. Однако, использование чисел допускает одинаковую обработку всех групп, независимо от количества содержащихся в них игроков. ** Обратите внимание, что в очень простом случае, когда каждый ПНГ является одной цифрой, строка может рассматриваться как число, которое становится все больше и больше по мере перехода к каждой новой перестановке: 234, 243, 324, 342, 423, 432. *** Конечно, эта равноценность никоим образом не общая, в данном случае она вызвана только тем, что рассматривался только один элемент! |
D.2 Обмены в однородных группах или остатках (начальная подгруппа S1 ↔ начальная подгруппа S2)
Обмен в однородных группах (также называемый обмен резидентами) это обмен двух групп ПНГ одинакового размера (представляющих всех игроков-резидентов), между начальными подгруппами S1 и S2.
| Обмениваемые наборы, конечно, должны иметь одинаковый размер, потому что, если бы это было не так, надо было изменить размеры подгрупп S1 и S2. |
Чтобы отсортировать все возможные обмены резидентами, применяйте следующие правила сравнения двух обменов резидентами в указанном порядке (т.е., если правило не различает два обмена, переходите к следующему обмену).
| Однако, чтобы оценить "вес" изменения, необходимо учитывать не только размер обмениваемых наборов, но и выбор игроков. Для этого нужен набор критериев, учитывающих различные аспекты этого выбора. Целью, как всегда, является “минимальное возмущение”, т.е., попытка создать пару, максимально похожую на естественную. |
Приоритет отдается обмену, имеющему:
a. наименьшее количество обмениваемых ПНГ (например, обмен только одного ПНГ лучше, чем обмен двух).
| Первый критерий - это, конечно, количество участников: чем меньше, тем лучше! |
b. самую маленькую разность между суммой ПНГ, перемещаемых из начальной подгруппы S2 в подгруппу S1, и суммой ПНГ, перемещаемых из начальной подгруппы S1 в подгруппу S2 (например, в группе из одиннадцати игроков, обмен 6-ого с 4-ым лучше, чем обмен 8-ого с 5-ым; аналогично обмен 8+6 с 4+3 лучше, чем обмен 9+8 с 5+4; и так далее).
| С теоретической точки зрения все игроки в подгруппе S1 должны быть сильнее любого игрока подгруппы S2. Поэтому, когда нужно поменять местами двух игроков в подгруппах, пытаемся выбрать самого слабого игрока в подгруппе S1 и поменять его на самого сильного из подгруппы S2. ПНГ используется для выбора игрока как можно более низкого ранга из подгруппы S1 и игрока как можно более высокого ранга из подгруппы S2, а затем они меняются местами, при этом предполагается, что более высокий ранг должен указывать на более сильного игрока. Таким образом, разница между обмениваемыми номерами является (или, по крайней мере, должна быть) прямой мерой разницы в (оценочной) силе и поэтому должна быть как можно меньше. |
c. самую большую разность ПНГ среди перемещаемых из начальной подгруппы S1 в подгруппу S2 (например, перемещение 5-ого из S1 в S2 лучше, чем перемещение 4-ого; аналогично, 5-2 лучше, чем 4-3; 5-4-1 лучше, чем 5-3-2; и так далее).
| Если два возможных варианта выбора игроков для обмена показывают одинаковую разницу в сумме их соответствующих ПНГ, выбирается вариант, который нарушает подгруппу S1 как можно меньше, т.е., тот, в котором игрок (с самым высоким ПНГ) из подгруппы S1 имеет более низкий ранг. В примере 5-2 лучше, чем 4-3, потому что обмен № 5 лучше, чем обмен № 4. Точно так же (5, 4, 1) является лучшим выбором, чем (5, 3, 2), потому что обмен № 4 лучше, чем обмен № 3*. * Иногда, как это происходит в приведённом выше примере, можно в конечном итоге обменять игрока более высокого ранга в качестве побочного эффекта вынужденного обмена на игрока возможно самого низкого ранга. Чтобы понять это, надо помнить, что происходит обмен не “нескольких одиночных игроков”, а целого набора их, и надо просто решить, лучше или хуже один набор, чем другой. В этом случае (5, 4, 1) лучше, чем (5, 3, 2), поэтому обменивается успешный игрок № 1, так как это средство обмена № 4, а не № 3. |
d. самую маленькую. разность ПНГ среди перемещаемых из начальной подгруппы S2 в подгруппу S1 (например, перемещение 6-ого из S2 в S1 лучше, чем перемещение 7-ого; аналогично, 6-9 лучше, чем 7-8; 6-7-10 лучше, чем 6-8-9; и так далее).
| Наконец, оптимизировав разницу в рангах и возмущение в подгруппе S1, можно оптимизировать возмущение и в подгруппе S2. В отличие от подгруппы S1, сейчас надо попытаться обменять возможно самый низкий ПНГ. Поэтому 6-9 лучше, чем 7-8, потому что обмен № 6 лучше, чем обмен № 7 и так далее. |
D.3 Обмены в неоднородных группах (начальная подгруппа S1 ↔ начальные подвешенные игроки)
Обмен в неоднородной группе (также называемый обменом спущенных игроков) представляет собой обмен двух групп ПНГ одинакового размера (все они представляют спущенных игроков) между начальной подгруппой S1 и начальными подвешенными игроками.
| Здесь изменяется состав набора спариваемых спущенных игроков. Конечно, это изменение может произойти только при M1 < M0*, потому что только в этой ситуации существуют подвешенные игроки. Это означает, что надо выбрать, каких спущенных игроков исключить из спаривания. Иногда решение лёгкое, например, может быть несколько несовместимых спущенных игроков, и тогда не может быть выбора вообще**. * См. Статью B.1. ** Напоминаем, что из-за критерия C.7 спущенные из предыдущей группы (т.е. спущенные игроки текущей группы) игроки уже были оптимизированы. Таким образом, если здесь имеется несовместимость, значит, альтернативы нет вообще. Следовательно, нет возврата к предыдущей группе («отступление»). |
Чтобы отсортировать все возможные обмены спущенных игроков, применяйте следующие правила сравнения двух обменов спущенных игроков в указанном порядке (т.е. если правило не различает два обмена, переходите к следующему) к игрокам, которые находятся в новой после обмена подгруппе S1.
| Если есть выбор, начинаем с попытки спарить как можно больше спущенных игроков и игроков как можно более высокого ранга [Статья B.2]. Если необходимо изменить этот начальный состав, надо применить обмен спущенных игроков. Следующие критерии позволяют определить приоритет среди всех возможных обменов. Отметим что этот результат достигается путём проверки состава новой подгруппы S1, а не подвешенных игроков. |
Приоритет отдаётся обмену, который даёт подгруппу S1, имеющую:
a. самую высокую разность очков среди игроков, представленных их ПНГ (это происходит автоматически в соответствии с критерием C.6, который говорит о сведении к минимуму разности очков в группе).
| Для поспешного читателя может показаться, что спаривание игрока с более низкими очками даст более низкую разность очков и, следовательно, более низкую РО. Конечно, это определённо неправильно! При переводе игрока с более высокими очками в группу подвешенных игроков, этот игрок будет спускаться, следовательно, соответствующая РО, которая рассчитывается с искусственным значением, определённым в Статье A.8, будет очень высокой. Чтобы свести к минимуму РО, подвешенных игроков должно быть минимальное количество, и у них должны быть как можно более низкие очки. Следовательно, соответствие критерию C.6, который предписывает нам минимизировать РО, автоматически удовлетворяет и этому критерию. Также обращаем внимание, что количество обмениваемых игроков не так уж и важно. Например, рассмотрим подгруппу S1 с тремя игроками и группу с двумя подвешенными игроками: в некоторых случаях обмен двух игроков более низкого ранга может дать лучшие результаты, чем обмен только одного игрока более высокого ранга. |
b. самое низкое лексикографическое (отсортированное по возрастанию) значение ПНГ.
| Надо стремиться соответствовать этому критерию. Если игроки имеют одинаковое количество очков, необходимо выбирать игроков более низкого ранга. Это легко сделать, сравнив группы игроков, которые вошли в подгруппу S1 после обмена, точно так же, как это делалось в предыдущих случаях. |
Каждый раз, когда сортировка будет создана, любое применение соответствующих правил D.1, D.2 или D.3 будет выбирать новый объект в порядке сортировки.
| Если повезет, то первая попытка перестановки, обмена или обмена спущенных игроков даст желаемый результат. Однако, часто приходится сделать несколько попыток, пока не получим успешную. В этом случае необходимо следовать порядку (последовательности), установленному тремя вышеприведёнными правилами. В идеале надо начинать с установления полного перечня всех возможных преобразований (будь то перестановки или обмены любого вида), перебирая список правил D.1, D.2 или D.3 (в случае необходимости), а затем пробуя одно за другим, пока не найдётся первое полезное преобразование*. * В обычной практике обмены и перестановки пробуются вместе (вероятно, при каждом обмене пробуется одна или несколько перестановок). Во избежание ошибок рекомендуется помечать последнее преобразование (каждого вида), чтобы при следующей попытке быть уверенным, какой элемент последовательности является следующим. |