Жадные идеи и их ловушки

Жадный алгоритм устроен предельно просто: на каждом шаге делаем то, что выглядит лучше всего прямо сейчас, и никогда не возвращаемся назад.

Набрать сумму 87 монетами 1, 2, 5, 10, 20, 50? Берём 50, потом 20, потом 10, потом 5, потом 2. Пять монет, и это оптимум.

Такие решения короткие и быстрые. Проблема в другом.

Та же идея, другие монеты

Пусть монеты 1, 3 и 4, а набрать надо 6.

Жадность берёт 4, потом остаётся 2 — это 1 и 1. Три монеты.

А правильный ответ — 3 и 3. Две монеты.

Алгоритм не изменился ни на строку. Изменились входные данные — и он перестал быть верным.

В этом вся тема занятия. Придумать жадность легко, почти всегда она приходит в голову первой. Трудно понять, верна ли она. И само по себе «выглядит разумно» здесь ничего не значит: только что мы видели идею, которая выглядит совершенно разумно и при этом неверна.

Есть рассуждение, которое превращает «кажется верным» в «верно». Оно называется обменным аргументом.

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

На примере

Задача: дано много отрезков, выбрать как можно больше попарно непересекающихся.

Жадная идея: брать отрезок, который заканчивается раньше всех, потом первый следующий, который с ним не пересекается, и так далее.

Почему это верно? Пусть есть оптимальный ответ, и первый отрезок в нём — не тот, что заканчивается раньше всех. Заменим его на наш, самый ранний по правому концу. Он заканчивается не позже, значит всем остальным выбранным отрезкам он мешает не больше прежнего — они как были непересекающимися, так и остались. Количество отрезков не изменилось, а первый шаг стал жадным.

Повторяя это рассуждение, превращаем весь оптимальный ответ в жадный, ни разу не потеряв в количестве. Значит жадный ответ — тоже оптимальный.

Что здесь важно

Аргумент опирается на конкретное свойство: «заканчивается раньше — мешает меньше». Никакого общего правила «жадность работает, если задача про максимум» нет. Каждый раз ищется своя причина.

Если причину найти не удаётся — это не доказательство неверности, но серьёзный повод поискать контрпример.

Какое из утверждений верно?

Это главный практический навык занятия. Контрпримеры почти всегда крошечные.

Начинайте с двух-трёх элементов. Если жадность неверна, она обычно ломается уже там. Пример из первого блока — три отрезка. Пример с монетами — сумма 6.

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

Сравните с полным перебором. Самый надёжный способ. Пишем заведомо правильное, но медленное решение — перебор всех вариантов, — и на маленьких случайных входах сравниваем ответы:

from itertools import permutations

def slow(a):
    best = None
    for order in permutations(a):     # все порядки — заведомо верно
        value = check(order)
        if best is None or value < best:
            best = value
    return best

for test in range(1000):
    a = random_list(n=6)              # маленький вход!
    if greedy(a) != slow(a):
        print("нашёлся:", a)
        break

Такая проверка называется стресс-тестом. Она не доказывает, что жадность верна, — но если контрпример существует, на тысяче случайных шестёрок он почти наверняка найдётся. Полчаса на стресс-тест дешевле, чем неверное решение на олимпиаде.

И обратите внимание: перебор пишется намеренно тупо. Его задача — быть очевидно правильным, а не быстрым.

Монеты достоинством 1, 5 и 8, набрать нужно сумму 15.

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

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

Когда ключ не очевиден

Бывает, что ключ — не одно из данных чисел, а их комбинация. Классический пример: работы выполняются по одной, работа $i$ занимает $t_i$ минут и приносит штраф $w_i$ за каждую минуту до своего завершения.

Что ставить раньше — короткую работу или дорогую? Сравним два соседних порядка. Если сначала $i$, потом $j$, лишний штраф равен $t_i \cdot w_j$: работа $j$ ждёт время $t_i$. Если наоборот — $t_j \cdot w_i$.

Значит $i$ выгодно ставить раньше, когда

Сортируем по отношению $t/w$ — и всё. Заметьте, как это получилось: не догадкой, а сравнением двух соседей. Этот приём работает в большинстве задач «в каком порядке делать».

Рюкзак с неделимыми предметами. Если груз сыпучий и его можно брать частями, жадность по стоимости килограмма верна. Если предметы целые — неверна. Вместимость 10, предметы: (6 кг, 60), (5 кг, 45), (5 кг, 45). Стоимость килограмма у первого выше, жадность берёт его и больше ничего не помещает — 60. Оптимум: два вторых, 90. Такие задачи решаются динамическим программированием, до которого мы дойдём в восьмом модуле.

«Возьму побольше сейчас». В задаче про смену знаков заманчиво поменять знак у самого большого по модулю отрицательного числа и остановиться. Но если действий больше, чем отрицательных чисел, остаток надо куда-то деть — и правильный ответ зависит от чётности остатка.

Неверный ключ, который почти работает. Сортировка по левому концу вместо правого, по длине вместо конца, по стоимости вместо стоимости килограмма. Такие решения проходят большинство тестов и падают на одном — потому что ошибка проявляется только в специальной конфигурации.

Как проверять себя

• два-три элемента — почти все контрпримеры такого размера;
• один огромный элемент среди маленьких;
• все элементы одинаковые;
• стресс-тест против перебора, если есть хоть малейшее сомнение.

Лестница прежняя: пять разминочных, семь основных, три со звёздочкой. Зачёт при десяти решённых.

Почти в каждой задаче первым делом надо решить, по какому ключу сортировать. Прежде чем писать код, скажите себе одним предложением, почему именно этот ключ.

А если предложение не складывается — придумайте контрпример к своей идее. Это быстрее, чем отлаживать неверное решение.

Задача: «дано $n$ отрезков; выберите как можно больше попарно непересекающихся». Совпадение концов считается пересечением.

Ученик рассуждает так: «короткие отрезки мешают остальным меньше, значит надо брать сначала самые короткие». И пишет:

n = int(input())
flat = list(map(int, input().split()))
segments = [(flat[2 * i], flat[2 * i + 1]) for i in range(n)]

segments.sort(key=lambda s: s[1] - s[0])

taken = []
for left, right in segments:
    if all(right < l or r < left for l, r in taken):
        taken.append((left, right))

print(len(taken))

Проверка на пересечение написана верно, и на многих тестах ответ правильный.

Постройте вход, на котором решение ошибается, объясните, почему рассуждение про «короткие мешают меньше» несостоятельно, и скажите, по какому ключу надо сортировать и почему.