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

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

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

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

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

Особенности

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

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

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

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

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

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

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

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

Типы

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

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

Теория

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

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

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

Матроиды

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

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

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

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

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

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

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

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

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

Приложения

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

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

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

Примеры

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

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

• Математический портал

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

Рекомендации

1. Блэк, Пол Э. (2 февраля 2005 г.). «жадный алгоритм». Словарь алгоритмов и структур данных . Национальный институт стандартов и технологий США (NIST) . Проверено 17 августа 2012 г.
2. Кормен и др. 2001, гл. 16
3. Гутин, Григорий; Эй, Андерс; Зверович, Алексей (2002). «Коммивояжер не должен быть жадным: анализ доминирования жадных эвристик для TSP». Дискретная прикладная математика . 117 (1–3): 81–86. дои : 10.1016/S0166-218X(01)00195-0 .
4. Файги, 1998 г.
5. Пападимитриу и Стейглиц, 1998 г.
6. Немхаузер, Вулси и Фишер, 1978 г.
7. Бухбиндер и др. 2014 год
8. Краузе и Головин 2014.
9. «Лекция 5: Введение в алгоритмы аппроксимации» (PDF) . Расширенные алгоритмы (2IL45) — Конспекты курса . ТУ Эйндховена. Архивировано (PDF) из оригинала 9 октября 2022 г.

Источники

• Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Штейн, Клиффорд (2001). «16 жадных алгоритмов». Введение в алгоритмы . МТИ Пресс. стр. 370–. ISBN 978-0-262-03293-3.
• Гутин, Григорий; Эй, Андерс; Зверович, Алексей (2002). «Коммивояжер не должен быть жадным: анализ доминирования жадных эвристик для TSP». Дискретная прикладная математика . 117 (1–3): 81–86. дои : 10.1016/S0166-218X(01)00195-0 .
• Банг-Йенсен, Йорген; Гутин, Григорий; Йо, Андерс (2004). «Когда жадный алгоритм дает сбой». Дискретная оптимизация . 1 (2): 121–127. дои : 10.1016/j.disopt.2004.03.007 .
• Бендалл, Гарет; Марго, Франсуа (2006). «Жадное сопротивление комбинаторных задач». Дискретная оптимизация . 3 (4): 288–298. дои : 10.1016/j.disopt.2006.03.001 .
• Файги, У. (1998). «Порог ln n для аппроксимации набора покрытия» (PDF) . Журнал АКМ . 45 (4): 634–652. дои : 10.1145/285055.285059. S2CID  52827488. Архивировано (PDF) из оригинала 9 октября 2022 г.
• Немхаузер, Г.; Уолси, Луизиана; Фишер, М.Л. (1978). «Анализ приближений для максимизации субмодулярных функций множества — I». Математическое программирование . 14 (1): 265–294. дои : 10.1007/BF01588971. S2CID  206800425.
• Бухбиндер, Нив; Фельдман, Моран; Наор, Джозеф (Сеффи); Шварц, Рой (2014). «Субмодульная максимизация с ограничениями мощности» (PDF) . Материалы двадцать пятого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . Общество промышленной и прикладной математики. дои : 10.1137/1.9781611973402.106. ISBN 978-1-61197-340-2. Архивировано (PDF) из оригинала 9 октября 2022 г.
• Краузе, А.; Головин, Д. (2014). «Максимизация субмодульной функции». В Бордо, Л.; Хамади, Ю.; Кохли, П. (ред.). Управляемость: практические подходы к сложным проблемам . Издательство Кембриджского университета. стр. 71–104. дои : 10.1017/CBO9781139177801.004. ISBN 9781139177801.
• Пападимитриу, Христос Х .; Стейглиц, Кеннет (1998). Комбинаторная оптимизация: алгоритмы и сложность . Дувр.

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

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