Подбор соперников: сортировка, обмен и паросочетание

Если ты знаешь, почему пары соседей по рейтингу оптимальны и когда подбор становится паросочетанием, листай до «Теперь сам».

Как думаешь, кому с кем играть

Первый в очереди - игрок с рейтингом 1510. Самый близкий к нему - 1480. Поставить их вместе - очевидно правильно? Или это может испортить пары для остальных?

Ответь себе до чтения. Для пары «1510 - 1480» разница 30 - лучше не бывает. Но 1480 мог быть единственным близким соседом кого-то ещё, а 1510 - хорошей парой для 1600. Жадный выбор для первого ничего не знает об остальных. Безопасно другое: отсортировать всех и ставить в пары соседей по списку - и это можно доказать.

На что это похоже

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

Механизм: обмен и увеличивающий путь

Почему пары соседей по рейтингу оптимальны. Возьми четырёх игроков a ≤ b ≤ c ≤ d. Разбить их на пары можно тремя способами: (a, b)(c, d) даёт (b − a) + (d − c), (a, c)(b, d) даёт (c − a) + (d − b), (a, d)(b, c) даёт (d − a) + (c − b). Первая сумма не больше двух других: из второй её получаем, вычтя 2(c − b) ≥ 0, из третьей - тоже. Значит, в любом разбиении пару «скрещённых» можно обменять на пару соседей, не проиграв, - это доказательство обменом из раздела 14. Как применить это ко всему списку: возьми самого слабого игрока a и его соседа по рейтингу b. Если b играет не с a, а с кем-то d, то четвёрка a, b, партнёр a, d - тот самый случай, и обмен ставит a с b, не ухудшив сумму. Дальше то же для оставшихся - и приходим к соседям по отсортированному списку.

Когда допустимы не все пары, сортировка не помогает: важно, КТО с кем может играть. Это двудольный граф - слева Север, справа Юг, ребро - допустимая пара, - и нужно наибольшее паросочетание. Жадность берёт первую свободную пару и может занять южанина, который был единственным вариантом для другого. Алгоритм Куна из раздела 12 для каждого северянина ищет увеличивающий путь: свободного южанина или занятого, чьего партнёра можно пересадить к другому свободному. Каждый найденный путь добавляет одну пару.

Правило

Без ограничений пары по рейтингу - соседи в отсортированном списке: обмен доказывает, что скрещённые пары не лучше. С ограничениями «кто с кем может» - наибольшее паросочетание с увеличивающими путями. Жадность «каждому лучшего из оставшихся» не гарантирует ни того, ни другого.

Разбор: восемь игроков, три способа

Восемь рейтингов. Перебор всех разбиений на пары - эталон; сортировка и жадность по очереди - кандидаты.

# восемь игроков в очереди на партию: рейтинги. Разбить на четыре пары
# так, чтобы сумма разниц рейтингов в парах была наименьшей
rejting = [1510, 1220, 1480, 1300, 1890, 1270, 1600, 1950]
perebrano = [0]

def perebor(svobodny):
    # все разбиения на пары: первый свободный - с каждым из остальных
    if len(svobodny) == 0:
        perebrano[0] = perebrano[0] + 1
        return 0
    a = svobodny[0]
    luchshee = -1
    for i in range(1, len(svobodny)):
        b = svobodny[i]
        ostatok = svobodny[1:i] + svobodny[i + 1:]
        s = abs(rejting[a] - rejting[b]) + perebor(ostatok)
        if luchshee == -1 or s < luchshee:
            luchshee = s
    return luchshee

def sosedi_po_rejtingu():
    # сортируем и берём пары соседей: 1-2, 3-4, ...
    r = sorted(rejting)
    s = 0
    for i in range(0, len(r), 2):
        s = s + r[i + 1] - r[i]
    return s

def zhadno():
    # первому в очереди - ближайшего по рейтингу из оставшихся, и т. д.
    svobodny = []
    for i in range(len(rejting)):
        svobodny.append(i)
    s = 0
    while len(svobodny) > 0:
        a = svobodny.pop(0)
        luchshij = 0
        for j in range(1, len(svobodny)):
            if (abs(rejting[a] - rejting[svobodny[j]])
                    < abs(rejting[a] - rejting[svobodny[luchshij]])):
                luchshij = j
        s = s + abs(rejting[a] - rejting[svobodny[luchshij]])
        svobodny.pop(luchshij)
    return s

vse = []
for i in range(len(rejting)):
    vse.append(i)
print("перебор:          ", perebor(vse), "| разбиений:", perebrano[0])
print("соседи в порядке: ", sosedi_po_rejtingu())
print("жадно по очереди: ", zhadno())

перебор:           380 | разбиений: 105
соседи в порядке:  380
жадно по очереди:  440

Перебор проверил 105 разбиений - для восьми игроков это 7 · 5 · 3 · 1, - и нашёл 380. Сортировка дала те же 380 за одну сортировку, без перебора. Жадность по очереди дала 440: первому в очереди, 1510, она отдала 1480, а потом игроку 1300 достался уже не сосед. Для 16 игроков разбиений 15 · 13 · … · 1 ≈ 2 · 10⁶, для 32 - порядка 10¹⁷: только сортировка. Граница правила: «наименьшая сумма разниц» - один из критериев. Если важнее, чтобы НИ ОДНА пара не была слишком неравной, это задача о наименьшем наибольшем расхождении - и там те же соседи тоже оптимальны, но доказывается это отдельно.

Разбор: Север против Юга

Шесть северян, шесть южан, у каждого северянина список допустимых соперников. Сколько партий удастся устроить одновременно?

# Турнир фракций: игрок Севера играет только с игроком Юга, и только если
# пинг между их серверами меньше 80 мс. mozhet[i] - кого с Юга может
# получить i-й игрок Севера. Нужно больше всего пар сразу.
mozhet = [[0, 1], [0], [1, 2], [2, 3], [3, 4], [4, 5]]
N_JUG = 6

def zhadno():
    # каждому по порядку - первого свободного из допустимых
    zanyat = [False] * N_JUG
    par = 0
    for spisok in mozhet:
        for j in spisok:
            if not zanyat[j]:
                zanyat[j] = True
                par = par + 1
                break
    return par

def najti_put(i, para_juga, byl):
    # Кун (раздел 12): ищем увеличивающий путь из игрока Севера i -
    # свободного южанина или южанина, чьего партнёра можно пересадить
    for j in mozhet[i]:
        if not byl[j]:
            byl[j] = True
            if (para_juga[j] == -1
                    or najti_put(para_juga[j], para_juga, byl)):
                para_juga[j] = i
                return True
    return False

def kun():
    para_juga = [-1] * N_JUG
    par = 0
    for i in range(len(mozhet)):
        if najti_put(i, para_juga, [False] * N_JUG):
            par = par + 1
    return [par, para_juga]

print("жадно:", zhadno(), "пар")
otvet = kun()
print("Кун:  ", otvet[0], "пар")
for j in range(N_JUG):
    if otvet[1][j] != -1:
        print("   Север", otvet[1][j], "- Юг", j)

жадно: 5 пар
Кун:   6 пар
   Север 1 - Юг 0
   Север 0 - Юг 1
   Север 2 - Юг 2
   Север 3 - Юг 3
   Север 4 - Юг 4
   Север 5 - Юг 5

Жадность отдала северянину 0 южанина 0 - первого в его списке, - и северянин 1, у которого в списке только южанин 0, остался без пары. Кун, дойдя до северянина 1, нашёл увеличивающий путь: южанин 0 занят северянином 0, но того можно пересадить к южанину 1. Все шесть в парах. Граница правила: Кун находит наибольшее ЧИСЛО пар, но не учитывает рейтинг. Если нужно и много пар, и равных, это паросочетание наименьшей стоимости - поток минимальной стоимости из раздела 12.

Что ломается без этого

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

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

Перебор «на всякий случай». Для честности решили перебрать все разбиения - на 32 игроках сервер не отвечает до конца сезона.

Зачем это в работе

Назначение курьеров на заказы, распределение задач по исполнителям с допусками, пары наставник - стажёр, распределение студентов по проектам - всё это паросочетания, а «пары по одной оси» - сортировка соседей. Отличить одно от другого просто: есть ли ограничения «кто с кем».

Теперь сам

1. Рейтинги 1000, 1100, 1350, 1400. Какие пары даст сортировка и какая сумма разниц? Сколько дала бы пара «1000 - 1400, 1100 - 1350»?
2. Почему 105 разбиений у восьми игроков?
3. Северян трое, южан трое: допустимы 0-0, 0-1, 1-0, 2-1. Сколько пар найдёт Кун?