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

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

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

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

• 1 Особенности
  • 1.1 Случаи отказа
• 2 Типа
• 3 Теория
  • 3.1 Матроиды
  • 3.2 Субмодульные функции
  • 3.3 Другие проблемы с гарантиями
• 4 Приложения
• 5 Примеры
• 6 См. Также
• 7 Примечания
• 8 Ссылки
• 9 Внешние ссылки

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

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

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

Свойство жадного выбора

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

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

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

Случаи сбоя

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

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

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

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

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

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

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

Matroids

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Жадная стратегия Эпсилон
• Жадный алгоритм для египетских дробей
• Жадный источник
• Матроид
• Первый поиск

1. ^Блэк, Пол Э. (2 февраля 2005 г.). "жадный алгоритм". Словарь алгоритмов и структур данных. США Национальный институт стандартов и технологий (NIST). Проверено 17 августа 2012 г.
2. ^Введение в алгоритмы (Кормен, Лейзерсон, Ривест и Штейн) 2001, глава 16 «Жадные алгоритмы».
3. ^Гутин Григорий; Йео, Андерс; Зверович, Алексей (2002). «Коммивояжер не должен быть жадным: анализ доминирования жадных эвристик для TSP». Дискретная прикладная математика. 117 (1–3): 81–86. doi : 10.1016 / S0166-218X (01) 00195-0.
4. ^U. Файги. Порог ln n для приближения установленного покрытия. Journal of the ACM, 45 (4): 634–652, 1998.
5. ^Пападимитриу, Христос Х. и Кеннет Стейглиц. Комбинаторная оптимизация: алгоритмы и сложность. Courier Corporation, 1998.
6. ^Г. Немхаузер, Л.А. Вулси и М.Л. Фишер. «Анализ приближений для максимизации функций субмодульного набора - I.» Математическое программирование 14.1 (1978): 265-294.
7. ^Н. Бухбиндер и др. "Субмодульная максимизация с ограничениями мощности." Труды двадцать пятого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам. Общество промышленной и прикладной математики, 2014.
8. ^Краузе, Андреас и Даниэль Головин. "Максимизация субмодульных функций." (2014): 71-104.
9. ^http://www.win.tue.nl/~mdberg/Onderwijs/AdvAlg_Material/Course%20Notes/lecture5.pdf

• Введение в алгоритмы (Cormen, Leiserson, Rivest, and Stein) 2001 г., глава 16. «Жадные алгоритмы»
• Гутин, Григорий; Йео, Андерс; Зверович, Алексей (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.
• U. Файги. Порог ln n для приближения установленного покрытия. Journal of the ACM, 45 (4): 634–652, 1998.
• G. Немхаузер, Л.А. Вулси и М.Л. Фишер. «Анализ приближений для максимизации функций субмодульного набора - I.» Математическое программирование 14.1 (1978): 265-294.
• N. Бухбиндер и др. "Субмодульная максимизация с ограничениями мощности." Труды двадцать пятого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам. Общество промышленной и прикладной математики, 2014.
• А. Краузе и Д. Головин. "Максимизация субмодульных функций." (2014): 71-104.

Викискладе есть материалы, связанные с Жадными алгоритмами.

• , Энциклопедия математики, EMS Press, 2001 [1994]
• Python greedy coin пример от Ноа Гифта.