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

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

История

Термин «жадный алгоритм» вошёл в обиход в середине XX века с развитием теории алгоритмов и комбинаторной оптимизации. Одним из первых формальных описаний жадного подхода считается алгоритм Краскала (1956 год) для нахождения минимального остовного дерева графа, предложенный Джозефом Краскалом. В 1957 году Роберт Прим разработал аналогичный алгоритм Прима. Оба алгоритма строят минимальное остовное дерево, последовательно добавляя рёбра с наименьшим весом, не образующие циклов. В 1970-х годах жадные алгоритмы получили широкое применение в задачах теории графов, расписаний, кодирования (алгоритм Хаффмана, 1952 год) и маршрутизации.

Принцип работы

Жадный алгоритм работает по следующей схеме:

1. Инициализация: задаётся начальное состояние (пустое решение, начальный узел графа и т.д.).
2. Выбор: на каждом шаге из множества возможных вариантов выбирается тот, который даёт наилучшее значение целевой функции (например, минимальный вес, максимальную прибыль) в текущий момент.
3. Принятие решения: выбранный вариант фиксируется и добавляется к текущему решению.
4. Проверка завершения: если достигнуто конечное условие (например, построено полное решение или исчерпаны все варианты), алгоритм останавливается; иначе возвращается к шагу 2.

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

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

Жадные алгоритмы эффективны для задач, обладающих двумя свойствами:

• Свойство жадного выбора (англ. greedy-choice property): глобально оптимальное решение может быть получено путём последовательного принятия локально оптимальных решений. То есть, если на каждом шаге выбирать наилучший локальный вариант, в итоге получится глобальный оптимум.
• Оптимальная подструктура (англ. optimal substructure): оптимальное решение задачи содержит в себе оптимальные решения её подзадач. Например, в задаче о минимальном остовном дереве оптимальное решение для всего графа включает оптимальные решения для его подграфов.

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

Примеры жадных алгоритмов

Алгоритм Хаффмана

Алгоритм Хаффмана (1952 год) используется для построения оптимального префиксного кода для сжатия данных без потерь. На каждом шаге из списка символов выбираются два с наименьшими частотами, объединяются в один узел с суммарной частотой, и этот узел возвращается в список. Процесс повторяется, пока не останется один корневой узел. Алгоритм гарантирует минимальную среднюю длину кодового слова.

Алгоритм Прима и алгоритм Краскала

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

Задача о рюкзаке (дробный вариант)

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

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

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

Применение

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

• Компьютерные сети: маршрутизация пакетов (алгоритм Дейкстры для кратчайших путей, хотя он не является жадным в строгом смысле, но использует жадный выбор на каждом шаге).
• Сжатие данных: кодирование Хаффмана, LZW (частично).
• Теория расписаний: задачи минимизации времени выполнения (например, алгоритм Джонсона для двух машин).
• Геоинформационные системы: построение кратчайших маршрутов, кластеризация.
• Финансы: задачи портфельной оптимизации (приближённые решения).
• Искусственный интеллект: поиск в пространстве состояний (например, алгоритм A* использует эвристику, но не является чистым жадным).

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

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

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

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

Интересные факты

• Жадные алгоритмы часто используются в онлайн-задачах, где решения принимаются последовательно без знания будущих данных (например, задача о наилучшем моменте покупки/продажи акций).
• В некоторых задачах (например, построение минимального остовного дерева) жадный подход даёт точное решение, что доказывается с помощью теории матроидов.
• Алгоритм Дейкстры (1959 год) для поиска кратчайших путей в графе с неотрицательными весами часто называют жадным, хотя он использует динамическое программирование для обновления расстояний.

Источники

• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. — 3-е изд. — М.: Вильямс, 2013.
• Седжвик Р., Уэйн К. Алгоритмы на Java. — 4-е изд. — М.: Вильямс, 2016.
• Кнут Д. Искусство программирования. Том 1. Основные алгоритмы. — 3-е изд. — М.: Вильямс, 2006.
• Papadimitriou C. H., Steiglitz K. Combinatorial Optimization: Algorithms and Complexity. — Dover Publications, 1998.