Введение

Последовательность локально оптимальных выборов

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

Конкретные сведения

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

Свойство жадного выбора: мы можем делать выбор, который кажется наилучшим в данный момент, а затем решать возникающие подзадачи. Выбор, сделанный жадным алгоритмом, может зависеть от сделанных ранее выборов, но не от будущих выборов или всех решений подзадач. Алгоритм итеративно делает один жадный выбор за другим, сводя каждую задачу к более простой. Иными словами, жадный алгоритм никогда не пересматривает свои решения. Это основное отличие от динамического программирования, которое является исчерпывающим и гарантированно находит оптимальное решение. После каждого этапа динамическое программирование принимает решения, основываясь на всех решениях, принятых на предыдущем этапе, и может пересмотреть алгоритмический путь к решению, пройденный на предыдущем этапе. Оптимальная подструктура: "Задача обладает оптимальной подструктурой, если оптимальное решение задачи содержит оптимальные решения подзадач."

Случаи неудачи

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

Матроиды

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

Субмодульные функции

Функция, определенная на подмножествах множества, называется субмодулярной, если для любого подмножества выполняется следующее:
Предположим, мы хотим найти множество, максимизирующее значение функции. Алгоритм жадного выбора, который строит множество путем последовательного добавления элемента, дающего наибольшее увеличение значения функции на каждом шаге, в результате выдает множество, значение функции для которого не меньше, чем (1 - 1/e) от оптимального значения. То есть, жадный алгоритм обеспечивает решение, которое по качеству не хуже оптимального решения в пределах постоянного множителя. Аналогичные гарантии могут быть доказаны и в случае дополнительных ограничений на выход, таких как ограничения на мощность множества, хотя часто для этого требуются незначительные модификации жадного алгоритма. Подробный обзор можно найти в [укажите источник].

Приложения

Алгоритмы жадности обычно (но не всегда) не находят глобально оптимальное решение, поскольку они, как правило, не обрабатывают все данные исчерпывающим образом. Они могут преждевременно принимать решения, что препятствует нахождению наилучшего общего решения на более поздних этапах. Например, все известные жадные алгоритмы раскраски графов для задачи раскраски графа и все другие NP-полные задачи не всегда находят оптимальные решения. Тем не менее, они полезны, так как их легко разработать и они часто дают хорошие приближения к оптимальному решению. Если для данного класса задач удается доказать, что жадный алгоритм обеспечивает глобальный оптимум, он обычно становится предпочтительным методом, поскольку он быстрее других методов оптимизации, таких как динамическое программирование. Примерами таких жадных алгоритмов являются алгоритм Краскала и алгоритм Прима для поиска минимальных остовных деревьев, а также алгоритм построения оптимальных деревьев Хаффмана. Жадные алгоритмы также применяются в сетевой маршрутизации. При жадной маршрутизации сообщение пересылается соседнему узлу, который "ближе всего" к пункту назначения. Понятие местоположения узла (и, следовательно, "близости") может определяться его физическим положением, как, например, в географической маршрутизации, используемой в ad hoc сетях. Местоположение также может быть полностью искусственной конструкцией, как в маршрутизации малого мира и распределенных хеш-таблицах.

Примеры

Для этого класса задач характерна задача выбора активностей, где цель состоит в выборе максимального количества активностей, не пересекающихся друг с другом. В компьютерной игре Crystal Quest для Macintosh цель – собрать кристаллы, что аналогично задаче коммивояжера. В игре есть демонстрационный режим, в котором используется жадный алгоритм для посещения каждого кристалла. Искусственный интеллект не учитывает препятствия, поэтому демонстрационный режим часто быстро завершается. Метод соответствия (matching pursuit) является примером жадного алгоритма, применяемого для приближения сигнала. Жадный алгоритм находит оптимальное решение задачи Мальфатти о нахождении трех непересекающихся окружностей внутри заданного треугольника, максимизирующих общую площадь окружностей; предполагается, что тот же жадный алгоритм оптимален для любого количества окружностей. Жадный алгоритм используется для построения дерева Хаффмана при кодировании Хаффмана, находя оптимальное решение. В обучении деревьев решений обычно используются жадные алгоритмы, однако они не гарантируют нахождение оптимального решения. Одним из таких популярных алгоритмов является алгоритм ID3 для построения дерева решений. Алгоритм Дейкстры и связанный с ним алгоритм поиска A* являются верифицируемо оптимальными жадными алгоритмами для поиска в графах и нахождения кратчайшего пути. Поиск A* является условно оптимальным, требуя "допустимой эвристики", которая не переоценивает стоимость пути. Алгоритмы Крускала и Прима – жадные алгоритмы для построения минимальных остовных деревьев заданного связного графа. Они всегда находят оптимальное решение, которое, в общем случае, может быть не единственным. Алгоритмы Sequitur и Lempel Ziv Welch – это жадные алгоритмы для грамматической индукции.