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

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

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

Специфика

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

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

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

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

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

Типы

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

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

Теория

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

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

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

Матроиды

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

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

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

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

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

Другие проблемы с гарантиями

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

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

Приложения

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

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

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

Примеры

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

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

Ссылки

^ Блэк, Пол Э. (2 февраля 2005 г.). "жадный алгоритм". Словарь алгоритмов и структур данных . Национальный институт стандартов и технологий США (NIST) . Получено 17 августа 2012 г.
^ Кормен и др. 2001, Гл. 16
^ Гутин, Грегори; Йео, Андерс; Зверович, Алексей (2002). «Коммивояжер не должен быть жадным: анализ доминирования эвристик жадного типа для TSP». Дискретная прикладная математика . 117 (1–3): 81–86. doi : 10.1016/S0166-218X(01)00195-0 .
^ DeVore, RA; Temlyakov, VN (1996-12-01). "Некоторые замечания о жадных алгоритмах". Advances in Computational Mathematics . 5 (1): 173–187. doi :10.1007/BF02124742. ISSN 1572-9044.
^ Фейге 1998
^ Пападимитриу и Стейглиц, 1998 г.
^ Немхаузер, Уолси и Фишер 1978
^ Бухбиндер и др. 2014
^ Краузе и Головин 2014
^ "Лекция 5: Введение в алгоритмы аппроксимации" (PDF) . Advanced Algorithms (2IL45) — Course Notes . TU Eindhoven. Архивировано (PDF) из оригинала 2022-10-09.

Источники

Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Штейн, Клиффорд (2001). «16 жадных алгоритмов». Введение в алгоритмы . МТИ Пресс. стр. 370–. ISBN 978-0-262-03293-3.
Гутин, Грегори; Йео, Андерс; Зверович, Алексей (2002). «Коммивояжер не должен быть жадным: анализ доминирования эвристик жадного типа для TSP». Дискретная прикладная математика . 117 (1–3): 81–86. doi : 10.1016/S0166-218X(01)00195-0 .
Банг-Йенсен, Йорген; Гутин, Грегори; Йео, Андерс (2004). «Когда жадный алгоритм терпит неудачу». Дискретная оптимизация . 1 (2): 121–127. doi : 10.1016/j.disopt.2004.03.007 .
Бендалл, Гарет; Марго, Франсуа (2006). «Сопротивление жадного типа комбинаторных задач». Дискретная оптимизация . 3 (4): 288–298. doi : 10.1016/j.disopt.2006.03.001 .
Feige, U. (1998). "Порог ln n для аппроксимации покрытия множеств" (PDF) . Journal of the ACM . 45 (4): 634–652. doi :10.1145/285055.285059. S2CID 52827488. Архивировано (PDF) из оригинала 2022-10-09.
Nemhauser, G.; Wolsey, LA; Fisher, ML (1978). "Анализ приближений для максимизации субмодулярных функций множеств — I". Математическое программирование . 14 (1): 265–294. doi :10.1007/BF01588971. S2CID 206800425.
Бухбиндер, Нив; Фельдман, Моран; Наор, Джозеф (Сеффи); Шварц, Рой (2014). "Субмодулярная максимизация с ограничениями мощности" (PDF) . Труды двадцать пятого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . Общество промышленной и прикладной математики. doi :10.1137/1.9781611973402.106. ISBN 978-1-61197-340-2. Архивировано (PDF) из оригинала 2022-10-09.
Krause, A.; Golovin, D. (2014). "Submodular Function Maximization". В Bordeaux, L.; Hamadi, Y.; Kohli, P. (ред.). Tractability: Practical Approaches to Hard Problems . Cambridge University Press. стр. 71–104. doi :10.1017/CBO9781139177801.004. ISBN 9781139177801.
Пападимитриу, Христос Х.; Стейглиц , Кеннет (1998). Комбинаторная оптимизация: алгоритмы и сложность . Дувр.

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

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

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