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

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

¶Основные принципы

Жадная стратегия основана на трёх ключевых компонентах:

• Множество кандидатов — элементы, из которых формируется решение;
• Функция выбора — правило, определяющее, какой кандидат является «наилучшим» на текущем шаге;
• Функция проверки — критерий, оценивающий, допустимо ли добавление выбранного кандидата к формируемому решению.

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

¶Свойства и условия применимости

Жадные алгоритмы дают точный результат только при выполнении двух фундаментальных свойств задачи:

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

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

¶Классические примеры

¶Минимальное остовное дерево

Алгоритм Прима начинает с произвольной вершины и на каждом шаге добавляет ребро минимального веса, соединяющее построенное дерево с новой вершиной. Алгоритм Краскала сортирует все рёбра по возрастанию веса и последовательно добавляет их, если они не образуют цикл. Оба алгоритма имеют сложность O(E log V) и широко применяются при проектировании сетей связи и маршрутизации.

¶Поиск кратчайших путей

Алгоритм Дейкстры находит кратчайшие расстояния от исходной вершины до всех остальных в графе с неотрицательными весами рёбер. На каждом шаге выбирается непосещённая вершина с минимальной текущей оценкой расстояния. Алгоритм лежит в основе многих сетевых протоколов маршрутизации.

¶Задача о размене монет

При наличии неограниченного запаса монет номиналом 1, 5, 10, 25 копеек жадный алгоритм, последовательно выбирающий монету наибольшего номинала, не превышающую остаток, даёт оптимальное решение для большинства реальных валютных систем. Однако для произвольных наборов номиналов (например, 1, 3, 4) жадная стратегия может дать неоптимальный результат: для суммы 6 она предложит 4 + 1 + 1 вместо 3 + 3.

¶Применение в информатике

¶Кодирование Хаффмана

Алгоритм Хаффмана строит префиксный код с минимальной избыточностью для сжатия данных. На каждом шаге два символа с наименьшей частотой встречаемости объединяются в узел дерева. Результирующий код используется в форматах JPEG, MP3 и ZIP.

¶Задачи планирования

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

¶Разбиение графа

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

¶Задачи, где жадность не работает

Существует ряд хорошо известных задач, для которых жадный подход принципиально непригоден:

• Задача коммивояжёра — жадный выбор ближайшего непосещённого города часто приводит к существенно неоптимальному маршруту;
• Задача о рюкзаке — в дискретном варианте выбор предметов с наибольшим отношением ценности к весу не гарантирует оптимальности;
• Задача о сумме подмножества — выбор наибольшего допустимого элемента не всегда приводит к точному решению.

Для таких задач применяются методы динамического программирования, ветвей и границ либо приближённые метаэвристики.

¶Сравнение с другими подходами

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

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

¶Практическая значимость

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

В комбинаторной оптимизации жадные алгоритмы служат базой для разработки более сложных методов: например, жадная инициализация используется в генетических алгоритмах и имитации отжига. В теории приближённых алгоритмов жадные стратегии часто обеспечивают гарантированные коэффициенты аппроксимации для NP-трудных задач, таких как задача о покрытии множества.

¶Ограничения и критика

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

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