Greedy Algorithms

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

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

Вторая половина предложения и есть весь приём. Без неё это не алгоритм, а догадка; с ней — самое быстрое решение задачи, обычно сортировка плюс один проход.

intervals.sort(key=lambda x: x[1])   # по правому концу

taken = 0
last_end = -inf

for start, end in intervals:
    if start >= last_end:            # не пересекается с уже взятым
        taken += 1
        last_end = end

return taken

1. Сформулировать критерий одной фразой: что значит «лучший» на текущем шаге.
2. Предположить, что существует оптимум, отличающийся от жадного решения.
3. Найти первое место расхождения и обменять там выбор на жадный.
4. Показать, что после обмена решение осталось допустимым и не стало хуже.

Сложность почти всегда определяется сортировкой: $O(n\log n)$ времени и $O(1)$ дополнительной памяти, если сортировать на месте. Сам проход линеен.

Аргумент обмена для интервалов выглядит так. Пусть в оптимальном расписании первой стоит встреча $X$, а жадность берёт $Y$ — ту, что заканчивается раньше всех. Заменим $X$ на $Y$: $Y$ заканчивается не позже $X$, значит все остальные встречи оптимума по-прежнему помещаются. Размер решения не изменился, а совпадение с жадным увеличилось на один шаг. Повторяя обмен, получаем, что жадное решение не хуже оптимального.

Есть и вторая формулировка того же — «жадный идёт впереди»: после каждого шага частичное жадное решение не хуже любого другого решения той же длины. Для интервалов она короче: после $k$ взятых встреч жадность освобождает зал раньше всех остальных вариантов.

номиналы:  1, 3, 4      набрать 6

жадно:     4 + 1 + 1   = три монеты
оптимум:   3 + 3       = две монеты

рюкзак 10 кг

A:  6 кг, 30    ->  5.0 за кг
B:  5 кг, 20    ->  4.0 за кг
C:  5 кг, 20    ->  4.0 за кг

жадно:   берём A, дальше ничего не влезает   = 30
оптимум: B + C                                = 40

• Привычные номиналы обманывают. На наборе 1, 2, 5, 10 жадность верна, поэтому ошибка проходит все «обычные» тесты.
• Неверный ключ сортировки. По длительности или по началу задача о максимуме встреч ломается — контрпример строится за секунды.
• Границы интервалов. Строгое или нестрогое сравнение концов меняет ответ.
• Починка критерия вторым критерием. Если первый контрпример нашёлся, найдётся и второй: задача просто не жадная.

1. Почему в задаче о максимуме встреч сортируют по правому концу, а не по левому или по длительности?
2. Постройте контрпример к жадному размену для номиналов 1, 5, 12.
3. Минимум залов: что именно хранится в куче и почему ответ — её максимальный размер?
4. Чем дробный рюкзак отличается от целочисленного настолько, что в одном жадность верна, а в другом нет?
5. Сформулируйте аргумент обмена для кода Хаффмана: почему два самых редких символа можно слить первыми?