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

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

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

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

Главный вопрос перед применением метода: можно ли доказать, что выбранный сейчас вариант безопасен? Если доказательства нет, нужно сравнить жадный способ с динамическим программированием или перебором.

Как работает подход

У жадного алгоритма обычно есть три составляющие. Сначала определяется критерий выбора: максимальная прибыль, минимальное время, самый ранний конец или наибольший доступный номинал. Затем выбирается один объект и фиксируется. После этого задача уменьшается: выбранный объект больше не рассматривается, а алгоритм повторяет шаг.

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

отсортировать занятия по времени окончания
последнееОкончание ← −∞
для каждого занятия:
если начало ≥ последнееОкончание:
выбрать занятие
последнееОкончание ← конец занятия

Сортировка обычно занимает O(n log n), а один проход после неё — O(n). Поэтому общий порядок времени — O(n log n).

Разобранный пример: выбор занятий

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

A: 1–4
B: 3–5
C: 0–6
D: 5–7
E: 8–9

Сначала сортируем занятия по окончанию: A заканчивается в 4, B — в 5, C — в 6, D — в 7, E — в 9. Выбираем A: оно заканчивается в 4. B и C начинаются раньше 4, поэтому пересекаются с A и пропускаются. D начинается в 5, значит, его можно взять. Теперь последнее окончание равно 7. E начинается в 8, поэтому тоже подходит.

выбраны: A, D, E
количество: 3
проверка: 1–4 → 5–7 → 8–9

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

Где жадность работает

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

Задача	Жадный выбор	Что проверить
Занятия	Самое раннее окончание	Нет пересечения
Крускал	Самое короткое ребро	Не образуется цикл
Размен	Крупнейшая подходящая монета	Система номиналов

С разменом нужна осторожность. Для монет 1, 3 и 4 сумма 6 набирается жадно так: 4 + 1 + 1, всего три монеты. Но вариант 3 + 3 использует две. Значит, критерий «брать крупнейшую монету» здесь не всегда даёт минимум.

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

Типичные ошибки и проверка

Первая ошибка — сортировать по неправильному полю. Для выбора занятий сортировка по началу или длительности не гарантирует оптимум. Вторая — запрещать касание интервалов. Если условие допускает занятия 2–5 и 5–8, проверка должна быть начало ≥ последнееОкончание, а не начало > последнееОкончание.

Третья ошибка — забывать обновлять состояние после выбора. Переменная последнего окончания должна измениться только тогда, когда занятие действительно добавлено. Четвёртая — считать, что любой жадный алгоритм автоматически правильный. Сначала найди контрпример или доказательство.

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

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

Что запомнить

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

Запомни алгоритм действий: сформулируй цель, выбери локальный критерий, отсортируй объекты, пройди их один раз и проверь граничные случаи. Если пример с монетами или другой задачей показывает неудачу, не исправляй жадность случайными условиями — рассмотри другой метод.

Следующий шаг — зарегистрируйся и реши 5 заданий бесплатно. Так ты закрепишь идею на разных сюжетах и научишься отличать доказанный жадный подход от правдоподобной, но неверной догадки.