Сортировка и жадные алгоритмы

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

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

Зачем это нужно

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

Идея «на пальцах»

Жадность = «бери лучшее сейчас и не оглядывайся». Размен монет: чтобы выдать сумму минимумом монет, берём самые крупные, пока можно. Для стандартных номиналов (1, 2, 5, 10) это работает. Но для номиналов (1, 3, 4) и суммы 6 жадность даст 4+1+1 = 3 монеты, а оптимум — 3+3 = 2. Вот почему жадность нужно доказывать: одна и та же идея на одних данных оптимальна, на других — нет.

Классика: выбор максимума непересекающихся заявок

Дано n мероприятий с временем начала и конца. Нужно выбрать максимум непересекающихся. Какая жадность верна? Можно сортировать по началу, по длительности, по концу. Правильный ответ: по времени окончания, и каждый раз брать заявку, которая не пересекается с последней выбранной.

intervals = [(1, 3), (2, 5), (4, 7), (1, 8), (5, 9), (8, 10)]
intervals.sort(key=lambda p: p[1])     # сортируем по правому концу
count = 0
last_end = float("-inf")
chosen = []
for s, e in intervals:
    if s >= last_end:                  # не пересекается с предыдущей
        count += 1
        last_end = e
        chosen.append((s, e))
print("Максимум непересекающихся:", count)
print("Выбраны:", chosen)

Мы перебираем заявки в порядке возрастания конца и жадно берём каждую, что начинается не раньше окончания предыдущей. Сортировка — O(n log n), проход — O(n).

Вывод:

Максимум непересекающихся: 3
Выбраны: [(1, 3), (4, 7), (8, 10)]

Почему именно «по концу»: доказательство обменом

Главный инструмент доказательства жадности — аргумент обмена (exchange argument). Покажем, что жадный выбор не хуже любого оптимального.

Пусть существует оптимальное решение OPT. Рассмотрим заявку с самым ранним концом — назовём её g (её первой берёт жадность). Если OPT уже содержит g — отлично. Если нет, то в OPT есть какая-то первая по времени заявка x. Так как g заканчивается не позже x (мы выбрали самый ранний конец), мы можем заменить x на g: g точно не пересечётся с остальными заявками OPT (они начинались после конца x ≥ конца g). Размер решения не изменился, оно осталось допустимым — значит, существует оптимум, содержащий g. Дальше рассуждаем по индукции для оставшихся заявок. Вывод: жадность по концу даёт оптимум. Эта схема «возьми жадный элемент, обменяй его в любой оптимум без потери» — универсальна для доказательства жадных алгоритмов.

Ещё пример: минимизация времени ожидания

Есть задания с длительностями; нужно так упорядочить их в очереди, чтобы суммарное время ожидания всех было минимальным. Жадность: сортировать по возрастанию длительности (короткие — вперёд). Проверим на числах.

durations = [4, 1, 3, 2]
durations.sort()                  # короткие задания вперёд
wait = 0
total = 0
for d in durations:
    total += wait                 # это задание ждало, пока шли предыдущие
    wait += d
print("Порядок:", durations)
print("Суммарное время ожидания:", total)

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