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

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

Пример жадного алгоритма следующий. Вспомните задачу "Платная лестница" из контеста на ДП. Правильное решение в этой задаче — это именно динамика, но в этой задаче можно также придумать и следующее жадное решение (правда, неправильное). На каждом шагу у нас есть два варианта — подняться на следующую ступеньку или перепрыгнуть через ступеньку. Вот посмотрим, какой из этих двух вариантов дешевле, т.е. на какой из этих ступенек меньше цена, и сделаем такой шаг.

Конечно, это решение неправильное, вот пример. Если на ступеньках написаны следующие числа:

1 2 10 2

то жадный алгоритм увидит, что изначально у него есть два варианта: сходить на ступеньку с числом 1 или с числом 2 — и пойдет на ступеньку с числом 1, т.к. это дешевле. Но правильное решение здесь — пойти на ступеньку с числом 2, т.к. потом мы сможешь перепрыгнуть ступеньку с числом 10.

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

(Сразу отмечу, что нередко жадные алгоритмы хочется применить в задачах на ДП. Да, многие задачи на жадность и на ДП похожи, просто в жадном алгоритме вы доказываете, что вариантов рассматривать не надо, а в ДП вы их честно рассматриваете. Поэтому если жадность не работает, то подумайте, не получится ли тут придумать ДП. Но на самом деле есть и много задач на жадность, где ДП не особенно придумаешь, и много задач на жадность, которые вообще не похожи на ДП.)

Но бывают задачи, в которых жадность все-таки работает, в которых можно доказать, что жадный алгоритм корректен. На самом деле, в наиболее простых задачах корректность жадности очевидна (и на этом уровне у вас в основном будут именно задачи такого типа, более продвинутые будут на уровне 6Б), еще в некоторых задачах корректность жадности может быть не очевидна (или даже может быть несколько разных жадных алгоритмов, которые можно придумать, и непонятно, какой из них правильный), но вы можете написать жадность, отправить на проверку (если это возможно на конкретной олимпиаде) и сразу узнать, корректна она или нет. Наконец, даже если жадность некорректна, она нередко работает в простых случаях, поэтому жадные алгоритмы нередко неплохо подходят на роль частичных решений.

Как доказывать жадность?

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

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

Пример. Пусть у нас задача: есть $N$ вещей, каждая со своим весом. Надо выбрать как можно больше вещей так, чтобы суммарный вес не превосходил заданного числа $C$. Очевидное жадное решение: брать вещи, начиная с самой легкой, пока суммарный вес не превосходит $C$. Как только превзошел — все, выводим ответ.

Давайте докажем. Рассмотрим жадное решение, оно берет себе вещи в порядке возрастания веса. Рассмотрим оптимальное решение и рассмотрим первый шаг, когда в жадном решении мы отклонились от оптимального. Это значит, что в жадном решении мы взяли вещь (пусть это вещь $X$), которая не входит в оптимальное решение. Значит, в оптимальном решении должна быть какая-то вещь (пусть это вещь $Y$), которой нет в жадном, иначе в жадном решении было бы больше вещей, чем в оптимальном, что противоречит оптимальности. При этом вещь $Y$ не легче, чем вещь $X$, т.к. в жадном решении мы брали все вещи в порядке возрастания веса. Тогда возьмем оптимальное решение, и заменим в нем вещь $Y$ на вещь $X$. Суммарный вес вещей в оптимальном решении не увеличится, количество вещей не уменьшится, поэтому решение по-прежнему будет оптимальным. Но оно будет совпадать с жадным на шаг дальше. ЧТД.

Второй вариант доказательства подходит к тем задачам, где вам надо выбрать некоторый порядок предметов: набор предметов вам задан, а надо выбрать, в каком порядке их расположить, чтобы что-то оптимизировать. Тогда вы можете попробовать доказать, что предметы надо расположить в порядке возрастания некоторого параметра (это и будет жадным алгоритмом). Доказательство будет таким: пусть в оптимальном решении предметы идут не в таком порядке. Тогда найдем два соседних предмета, которые идут в неправильном порядке, и поменяем их местами, и докажем, что решение не ухудшится, а значит, останется оптимальным. Тогда очевидно, что жадное решение (которое расставляет предметы в порядке возрастания этого параметра) будет корректным.

Пример. В олимпиадах типа ACM участники решают задачи. За каждую решенную задачу они получают штраф, равный времени, прошедшему с начала тура до момента решения этой задачи. Предположим, что у нас есть идеальная команда, и она тратит $t_i$ минут на решение $i$-й задачи (и никогда не делает неудачных попыток). В каком порядке им надо решать задачи, чтобы получить минимальный штраф?

Жадный алгоритм: в порядке возрастания $t_i$. Доказательство. Пусть у нас есть оптимальное решение, в котором $t_i$ не отсортированы по возрастанию. Найдем две задачи, $i$ и $j$, такие, что в оптимальном решении мы решаем сначала решаем задачу $i$, а сразу после нее задачу $j$, при этом $t_i>=t_j$. Поменяем их местами. Что изменится в плане штрафного времени? Для всех задач, которые мы решали до этих двух, штрафное время не изменится. Для всех задач, которые мы решали после этих двух, штрафное время тоже не изменится. (Именно для этого мы и брали соседние задачи.) Штрафное же время по этим задачам было $t_i+(t_i+t_j)$, а стало $t_j+(t_i+t_j)$. Поскольку $t_i>=t_j$, то решение не ухудшилось, значит, оно осталось оптимальным. ЧТД.

(Оба доказательства выше в принципе можно переформулировать на доказательства от противного: что если оптимальное решение сильно отличается от жадного, то мы меняем оптимальное решение, получаем решение, которое строго лучше, значит, оптимальное решение было не оптимальным. Да, так доказывать тоже можно, но надо аккуратно обойтись со случаем равных значений — случаем $t_i=t_j$ или случаем двух вещей одного веса в первой задаче.)

На самом деле, второй вариант доказательства на самом деле позволяет придумывать жадность в тех задачах, где она не очевидна (если не поймете этот абзац, то не страшно). Если вам в задаче надо расположить объекты в некотором порядке, и вы не знаете, в каком, подумайте: пусть у вас есть некоторый порядок. Поменяем местами два соседних предмета, посмотрим, как изменится решение. Пусть оценка старого решения была $X$, а нового — $Y$ (это, конечно, функция решения). Напишем условие $X>Y$, т.е. что решение улучшилось. Попробуем его преобразовать так, чтобы свести все к характеристикам двух объектов, которые мы меняем местами. Тогда, может быть, мы обнаружим, что условие $X>Y$ эквивалентно условию $f(i)>f(j)$, где $i$ и $j$ — предметы, которые мы поменяли местами, а $f$ — какая-то функция. Тогда очевидно, что в правильном решении надо просто отсортировать предметы по значению функции $f$.