Сначала крупные: сортировка перед раздачей и граница 4/3

Если ты докажешь гарантию 3/2 для раздачи после сортировки и знаешь, откуда в точной оценке берётся 4/3, листай до «Теперь сам».

Как думаешь, что изменит одна сортировка

В прошлом уроке жадная раздача на худшем входе ошибалась почти вдвое: m(m − 1) единичных задач ложились ровно, а последняя длинная садилась сверху. Отсортируем задачи по убыванию до раздачи и больше ничего не тронем. Всё ещё жадность, всё ещё одна строка кода.

Ответь себе до чтения: какой станет гарантия? Останется двойка, потому что жадность есть жадность? Или одна сортировка доведёт до оптимума? Ни то ни другое. Гарантия падает с 2 − 1/m до 4/3 − 1/(3m), а оптимума сортировка не даёт: есть вход из пяти задач на двух серверах, где она ошибается на одну шестую.

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

Укладка багажника. Опытный водитель сначала ставит чемоданы, потом сумки, а мелочь распихивает по щелям в самом конце. Кто кладёт в порядке «как вынесли из квартиры», рискует, что последним вынесут самый большой чемодан - и он не влезет никуда, кроме как сверху.

Мелочь в конце безопасна: даже если положить её неудачно, перекос будет на размер этой мелочи. Ровно это и превращается в доказательство: перекос жадности не больше длины последней задачи, а последней после сортировки идёт короткая.

Механизм: почему последняя задача теперь короткая

Из прошлого урока: если позже всех закончилась задача ℓ, то длина расписания T ≤ P / m + p_ℓ, где P - вся работа. Первое слагаемое не больше оптимума всегда. Вся игра - во втором: насколько длинной может быть задача, которая закончилась последней.

Довод на 3/2. Задачи пронумерованы по убыванию: p₁ ≥ p₂ ≥ … ≥ pₙ.

случай 1: ℓ <= m
  задача ℓ попала на пустой сервер и стоит на нём одна:
  T = p_ℓ <= OPT
случай 2: ℓ > m
  задачи 1, 2, ..., m + 1 все не короче p_ℓ;
  m + 1 задач на m серверах - две из них в оптимуме на одном сервере,
  значит  OPT >= 2 · p_ℓ,  то есть  p_ℓ <= OPT / 2
  T <= P / m + p_ℓ <= OPT + OPT / 2 = 1,5 · OPT

Довод опирается на принцип ящиков: m + 1 предметов в m ящиках - хотя бы в одном ящике два. Новая нижняя граница 2 · p_{m+1} появилась только благодаря сортировке: без неё задача ℓ могла быть самой длинной.

Откуда 4/3. Если последняя задача не длиннее OPT / 3, та же оценка даёт T ≤ OPT + OPT / 3. Остаётся случай, когда все задачи до ℓ длиннее трети оптимума. Тогда в оптимальном расписании на сервере их не больше двух, и разбор случаев (здесь он не приводится - его можно найти у Грэма или в книге Уильямсона и Шмойса) показывает, что для таких входов раздача после сортировки оптимальна - раскладывать приходится только пары. Точная оценка Грэма (1969): 4/3 − 1/(3m).

Правило

Раздача по списку после сортировки по убыванию (LPT) даёт длину не больше (4/3 − 1/(3m)) · OPT. Простой довод на 3/2: последней кончается задача не длиннее OPT / 2, потому что первые m + 1 задач не короче её и две из них в оптимуме делят сервер. Ошибка жадности не больше длины последней задачи - сортировка делает её короткой.

Разбор: тот же вход и семейство худших входов

razdat - раздача по списку из прошлого урока, lpt - она же после сортировки. Сначала семь задач из прошлого урока, потом семейство входов, на котором гарантия LPT достигается: на m серверах по две задачи длины 2m − 1, 2m − 2, …, m + 1 и ещё три задачи длины m.

def razdat(zadachi, m):
    nagruzka = [0] * m
    for p in zadachi:
        luchshij = 0
        for i in range(1, m):
            if nagruzka[i] < nagruzka[luchshij]:
                luchshij = i
        nagruzka[luchshij] = nagruzka[luchshij] + p
    return max(nagruzka)

def lpt(zadachi, m):
    return razdat(sorted(zadachi, reverse=True), m)

print(razdat([3, 7, 5, 3, 1, 9, 1], 3), lpt([3, 7, 5, 3, 1, 9, 1], 3))
for m in [2, 3, 4, 5]:
    zadachi = []
    for d in range(2 * m - 1, m, -1):
        zadachi.append(d)
        zadachi.append(d)
    zadachi = zadachi + [m, m, m]
    print(m, zadachi, lpt(zadachi, m), 3 * m, 4 / 3 - 1 / (3 * m))

15 10
2 [3, 3, 2, 2, 2] 7 6 1.1666666666666665
3 [5, 5, 4, 4, 3, 3, 3] 11 9 1.222222222222222
4 [7, 7, 6, 6, 5, 5, 4, 4, 4] 15 12 1.25
5 [9, 9, 8, 8, 7, 7, 6, 6, 5, 5, 5] 19 15 1.2666666666666666

На входе из прошлого урока сортировка дала 10 вместо 15 - ровно оптимум. Девятка встала первой, и мелочь легла вокруг неё.

Семейство - честный худший случай. На двух серверах: 3, 3, 2, 2, 2. Сортировка кладёт тройки на разные серверы, двойки по одной к каждой - нагрузки 5, 5, - и последняя двойка садится сверху: 7. Оптимум 6: 3 + 3 и 2 + 2 + 2. Отношение 7 / 6 = 4/3 − 1/6. В общем случае ответ 4m − 1 против оптимума 3m. Оптимум собирается парами: задача длины d встаёт вместе с задачей 3m − d - обе есть во входе, - и каждая такая пара занимает сервер ровно на 3m; три задачи длины m занимают последний сервер на те же 3m. Столбец гарантии совпал с отношением ответ / оптимум на каждой строке: 11 / 9 = 1,222, 15 / 12 = 1,25, 19 / 15 = 1,267.

Разбор: гарантия против типичной ошибки

Гарантия описывает худший вход. Сколько алгоритм теряет на обычных? Сорок случайных наборов по десять задач длиной от 1 до 20, два сервера. Оптимум для двух серверов считается точно таблицей достижимых сумм из раздела о динамическом программировании: лучшее, что может взять первый сервер, - наибольшая достижимая сумма, не превышающая половины.

import random

def razdat(zadachi, m):
    nagruzka = [0] * m
    for p in zadachi:
        luchshij = 0
        for i in range(1, m):
            if nagruzka[i] < nagruzka[luchshij]:
                luchshij = i
        nagruzka[luchshij] = nagruzka[luchshij] + p
    return max(nagruzka)

def optimum_dvuh(zadachi):
    vsego = sum(zadachi)
    dostizhimo = [False] * (vsego + 1)
    dostizhimo[0] = True
    for p in zadachi:
        for s in range(vsego, p - 1, -1):
            if dostizhimo[s - p]:
                dostizhimo[s] = True
    s = vsego // 2
    while not dostizhimo[s]:
        s = s - 1
    return vsego - s

random.seed(22)
hudshee_z = 0
hudshee_l = 0
summa_z = 0
summa_l = 0
for opyt in range(40):
    zadachi = []
    for i in range(10):
        zadachi.append(random.randint(1, 20))
    opt = optimum_dvuh(zadachi)
    z = razdat(zadachi, 2) / opt
    l = razdat(sorted(zadachi, reverse=True), 2) / opt
    summa_z = summa_z + z
    summa_l = summa_l + l
    hudshee_z = max(hudshee_z, z)
    hudshee_l = max(hudshee_l, l)
print(round(summa_z / 40, 3), round(hudshee_z, 3))
print(round(summa_l / 40, 3), round(hudshee_l, 3))

1.062 1.2
1.009 1.039

Первая строка - раздача в порядке прихода: в среднем 6,2% сверх оптимума, худший из сорока - 20%. Вторая - после сортировки: 0,9% в среднем, 3,9% в худшем. Гарантии на двух серверах - 1,5 и 7/6 ≈ 1,167; на случайных входах оба алгоритма далеко от них.

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

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

Задачи приходят по одной. Сортировка требует знать все задачи заранее. Если задачи поступают потоком и решать надо сразу, LPT недоступна, и остаётся раздача по приходу с её 2 − 1/m. Сравнивать алгоритмы, не спросив, знаешь ли ты вход целиком, - ошибка постановки, а не выбора.

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

Ждут оптимума. LPT не точна: на 3, 3, 2, 2, 2 она даёт 7 при оптимуме 6. Точный ответ - задача о разбиении, NP-трудная. Если нужна точность выше 4/3, нужен другой инструмент - схема приближенияРазбирается в разделе 22, глава «Пределы приближения - PTAS, APX и почему дальше нельзя»: PTAS и FPTAS: точность по заказу и кто её не допускает с точностью по заказу.

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

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

Тот же приём в упаковке: архивы по дискам, контейнеры по узлам кластера, заказы по курьерам. Правило «сначала крупное» - не фольклор, а то, что убирает из оценки самый опасный член.

Теперь сам

1. Задачи 5, 5, 4, 4, 3, 3, 3, три сервера. Раздай по правилу LPT и найди оптимум. Совпало ли отношение с гарантией 4/3 − 1/9?
2. Почему в доводе на 3/2 нужны именно m + 1 задач не короче p_ℓ, а не m?
3. На четырёх серверах LPT дала 26. Какое наименьшее значение может иметь оптимум, если верить точной гарантии?