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

Жадные алгоритмы определяют минимальное количество монет, которое нужно отдать при внесении сдачи. Это шаги, которые большинство людей предприняло бы для имитации жадного алгоритма для представления 36 центов, используя только монеты со значениями {1, 5, 10, 20}. Монета с наибольшей стоимостью, меньше оставшейся причитающейся сдачи, является локальным оптимумом. (В общем, проблема внесения изменений требует динамического программирования для поиска оптимального решения; однако большинство валютных систем, включая евро и доллар США, являются частными случаями, когда жадная стратегия действительно находит оптимальное решение.)

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

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

Особенности

В общем, жадные алгоритмы состоят из пяти компонентов:

1. Набор кандидатов, из которого создается решение
2. Функция выбора, которая выбирает лучшего кандидата для добавления в решение.
3. Функция осуществимости, которая используется, чтобы определить, можно ли использовать кандидата для внесения вклада в решение.
4. Целевая функция, которая присваивает значение решению или частичному решению, и
5. Функция решения, которая укажет, когда мы нашли полное решение.

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

Жадный выбор собственности

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

Оптимальная подконструкция

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

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

Примеры того, как жадный алгоритм может не дать оптимального решения.

Начиная с A, жадный алгоритм, который пытается найти максимум по наибольшему наклону, найдет локальный максимум в точке «m», не обращая внимания на глобальный максимум в точке «M».

Чтобы получить наибольшую сумму, на каждом шаге жадный алгоритм будет выбирать то, что кажется оптимальным немедленным выбором, поэтому он выберет 12 вместо 3 на втором этапе и не достигнет лучшего решения, которое содержит 99.

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

Типы

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

• Чистые жадные алгоритмы
• Ортогональные жадные алгоритмы
• Расслабленные жадные алгоритмы

Теория

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

• Для каких проблем жадные алгоритмы работают оптимально?
• Для каких проблем жадные алгоритмы гарантируют приблизительно оптимальное решение?
• Для каких проблем жадный алгоритм гарантированно не даст оптимального решения?

Существует большое количество литературы, в которой даны ответы на эти вопросы как для общих классов задач, таких как матроиды , так и для конкретных задач, таких как набор покрытий .

Матроиды

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

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

Функция , определенная на подмножествах множества называется субмодулярной , если для каждого у нас есть что . ${\ displaystyle f}$${\ displaystyle \ Omega}$${\ Displaystyle S, Т \ substeq \ Omega}$${\ Displaystyle е (S) + е (T) \ geq f (S \ чашка T) + f (S \ cap T)}$

Предположим, кто-то хочет найти набор, который максимизирует . Жадный алгоритм, который создает набор , постепенно добавляя элемент, который увеличивается больше всего на каждом шаге, выдает на выходе набор, который не меньше . То есть, жадность работает с постоянным коэффициентом, равным оптимальному решению. ${\ displaystyle S}$${\ displaystyle f}$${\ displaystyle S}$${\ displaystyle f}$${\ Displaystyle (1-1 / е) \ макс _ {X \ substeq \ Omega} f (X)}$${\ displaystyle (1-1 / e) \ приблизительно 0,63}$

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

Прочие проблемы с гарантиями

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

• Установить обложку
• Проблема дерева Штейнера
• Балансировка нагрузки
• Независимый набор

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

Приложения

Жадные алгоритмы обычно (но не всегда) не могут найти глобально оптимальное решение, потому что они обычно не обрабатывают все данные исчерпывающе. Они могут слишком рано принять определенные решения, не позволяя им найти лучшее общее решение позже. Например, все известные алгоритмы жадной раскраски для задачи раскраски графа и всех других NP-полных задач не всегда находят оптимальные решения. Тем не менее они полезны, потому что они быстро придумываются и часто дают хорошие приближения к оптимуму.

Если можно доказать, что жадный алгоритм дает глобальный оптимум для данного класса проблем, он обычно становится методом выбора, поскольку он быстрее, чем другие методы оптимизации, такие как динамическое программирование . Примерами таких жадных алгоритмов Алгоритм Крускала и алгоритм Прима для нахождения минимального остовного дерева и алгоритм для нахождения оптимальных деревьев Хаффмана .

Жадные алгоритмы появляются и в сетевой маршрутизации . Используя жадную маршрутизацию, сообщение пересылается на соседний узел, который является «ближайшим» к месту назначения. Понятие местоположения узла (и, следовательно, «близость») может определяться его физическим местоположением, как при географической маршрутизации, используемой специальными сетями . Местоположение также может быть полностью искусственной конструкцией, как в случае с маршрутизацией в маленьком мире и распределенной хеш-таблицей .

Примеры

• Проблема выбора деятельности характерна для этого класса задач, где цель состоит в том, чтобы выбрать максимальное количество действий, которые не конфликтуют друг с другом.
• В компьютерной игре Crystal Quest для Macintosh цель состоит в том, чтобы собирать кристаллы аналогично задаче коммивояжера . В игре есть демонстрационный режим, в котором игра использует жадный алгоритм для перехода к каждому кристаллу. Искусственный интеллект не учитывает препятствия, поэтому демонстрационный режим часто заканчивается быстро.
• Поиск совпадения является примером жадного алгоритма , нанесенного на приближении сигнала.
• Жадный алгоритм находит оптимальное решение проблемы Малфатти о нахождении трех непересекающихся кругов внутри данного треугольника, которые максимизируют общую площадь кругов; предполагается, что один и тот же жадный алгоритм оптимален для любого числа кругов.
• Жадный алгоритм используется для построения дерева Хаффмана во время кодирования Хаффмана, где он находит оптимальное решение.
• При изучении дерева решений обычно используются жадные алгоритмы, однако они не гарантируют нахождение оптимального решения.
  • Одним из популярных таких алгоритмов является алгоритм ID3 для построения дерева решений.
• Алгоритм Дейкстров и соответствующий A * алгоритм поиска являются проверяемым оптимальными жадными алгоритмами поиска графов и кратчайшим путем нахождения .
  • Поиск * является условно оптимальным и требует « допустимой эвристики », которая не будет переоценивать стоимость пути.
• Алгоритм Крускала и алгоритм Прима жадные алгоритмы для построения минимальных остовных деревьев из заданного связного графа . Они всегда находят оптимальное решение, которое в целом может быть не уникальным.

Смотрите также

использованная литература

Источники

внешние ссылки

• «Жадный алгоритм» , Энциклопедия математики , EMS Press , 2001 [1994]
• Подарок, Ной. "Пример жадной монеты Python" .