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

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

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

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

Классический пример — размен монет

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

Сумма 47, номиналы 1, 5, 10, 25: берём 25 -> остаток 22 берём 10 -> остаток 12 берём 10 -> остаток 2 берём 1 -> остаток 1 берём 1 -> остаток 0 Итог: 25+10+10+1+1 = 5 монет

Когда жадность ошибается

Для некоторых наборов номиналов жадность даёт не лучший ответ. Пусть номиналы 1, 3, 4, и нужно набрать 6. Жадно: 4+1+1 = три монеты. А оптимально: 3+3 = две монеты. Значит, для этого набора жадный алгоритм неверен.

Задача	Жадность работает
Размен обычными монетами	да
Выбор непересекающихся занятий	да
Задача о рюкзаке (целочисленная)	нет

Условие применимости

Жадный алгоритм даёт верный ответ, если задача обладает свойством жадного выбора (локально лучший шаг входит в оптимальное решение) и оптимальной подструктуры (оптимальное решение состоит из оптимальных решений подзадач). Если эти свойства не выполнены, нужен другой метод, например динамическое программирование.

Задача о выборе занятий

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

Сравнение с перебором

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

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

Кратко о главном

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