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

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

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

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

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

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

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

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

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

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

Этот шаблон доказательства обычно следует следующим шагам (от противного):

1. Предположим, что существует оптимальное решение, отличное от жадного решения.
2. Определите первую точку, в которой оптимальное и жадное решения различаются
3. Докажите, что замена оптимального выбора на жадный выбор в этой точке не может ухудшить решение.
4. Заключите по индукции, что должно существовать оптимальное решение, идентичное жадному решению.

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

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

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

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

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

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

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

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

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

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

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

Аналогичные гарантии доказуемы, когда на выход накладываются дополнительные ограничения, такие как ограничения мощности ^{[9] , хотя часто требуются небольшие изменения в жадном алгоритме. См. [10]} для обзора.

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

• Установить обложку
• Задача о дереве Штейнера
• Балансировка нагрузки ^[11]
• Независимый набор

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

Этот раздел нуждается в расширении . Вы можете помочь, дополнив его. ( Июнь 2018 )

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

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

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

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

На Викискладе есть медиафайлы по теме Жадные алгоритмы .

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