Жадный алгоритм

Жадный алгоритм - это общее название для целой группы разных алгоритмов. Все эти алгоритмы объединены естественным соображением пытаться как можно быстрее и проще получить ответ на задачу.

Антагонистом жадных алгоритмов является динамическое программирование. Там мы не можем заранее сказать, какой ход будет оптимальным, поэтому считаются все состояния динамики. Однако некоторые задачи можно решать как жадностью, так и динамикой. Разница будет только в асимптотике полученного алгоритма и в приложенных усилиях (жадники бывают очень нетривиальными). Пример такой задачи --- Региональный этап, первый тур, 4 февраля 2017г. задача 2 (Калькулятор).

Классическим примером задачи на жадность является задача о распределении времени. Допустим, у нас есть ряд лекций, все хотят попастать в аудиторию $X$. Каждый лектор может прочитать свою лекцию только в аудитории $X$, причем ровно во время с $l_i$ по $r_i$. Во имя всеобщего образования надо организовать порядок лекций так, чтобы было прочитано максимальное их число. Формально это можно понимать, как размещение максимального количества непересекающихся отрезков на прямой.

Как такое решать?

Правильным решением будет отсортировать отрезки по возрастанию правых концов. Пройдемся по отсортированному массиву отрезков, поддерживая самую правую правую (с отрезками всегда так) границу взятого отрезка, назовем ее $B$. Пусть сейчас рассматривается отрезок $[l, r]$. Если $B \le l$, то можно взять этот отрезок и обновить $B \leftarrow r$. Иначе продолжаем проход по массиву.

Почему это правильно

А теперь будет весьма абстрактненько. Пусть есть оптимальный алгоритм, назовем его OPT, и наш алгоритм, назовем его OUR. Нааш цель - показать, что OUR дает ответ не хуже оптимального. Тут надо осознать, что в общем случае алгоритм OPT может быть любым, совсем любым. Мы допустим, что алгоритм OPT тоже поочередно добавляет в ответ отрезки. Упорядочим их по правому концу. Ограничимся таким уровнем строгости.

Таким образом, есть две последовательности отрезков, которые формируют два ответа. Пусть первые $k$ отрезков у двух последовательностей совпадают. Будем обозначать $a_i$ и $b_i$ - отрезки $i$ в OPT и OUR соответственно. У отрезка $x$ левый и правый концы обозначим $x.l$ и $x.r$ соответственно.

Посмотрим на отрезок $k+1$. По определению алгоритма OPT $b_{k+1}.r \le a_{k+1}.r$. Теперь поменяем в ответе алгоритма OPT отрезок $a_{k+1}$ на $b_{k+1}$. Правая граница либо останется на месте, либо сдвинется левее. Так как в оптимальном ответе отрезки уже отсортированы по правой границе, то остальные отрезки (с номерами больше $k+2$) не будут задеты этим изменением. Отрезки левее также не мешают, так как они совпадают с отрезками из OUR. При этом отрезок $b_{k+1}$ не мог бы войти в исходный ответ OPT позже или раньше, так как отрезки отсортированы по правому концу в обоих ответах.

Получаем, что замена не ухудшила ответ OPT. Значит, вывод оптимального алгоритма и нашего сопадает и на позиции $k+1$. По сути мы доказали шаг индукции. Тогда наш алгоритм дает оптимальный ответ.

Надеюсь, вы почувствовали, какими приятными бывают доказательства (строгие) жадных алгоритмов.