Жадный алгоритм является любым алгоритмом , который следует за решением проблем эвристического сделать локально оптимальный выбор на каждом этапе. [1] Во многих задачах жадная стратегия обычно не дает оптимального решения, но, тем не менее, жадная эвристика может дать локально оптимальные решения, приближающие глобально оптимальное решение за разумный промежуток времени.
Например, жадная стратегия для задачи коммивояжера (имеющая высокую вычислительную сложность) представляет собой следующую эвристику: «На каждом этапе путешествия посещайте ближайший не посещаемый город». Эта эвристика не предназначена для поиска лучшего решения, но завершается разумным количеством шагов; поиск оптимального решения такой сложной проблемы обычно требует неоправданно большого количества шагов. В математической оптимизации жадные алгоритмы оптимально решают комбинаторные задачи, обладающие свойствами матроидов , и дают приближения с постоянным коэффициентом к задачам оптимизации с субмодульной структурой.
Особенности [ править ]
В общем, жадные алгоритмы состоят из пяти компонентов:
- Набор кандидатов, из которого создается решение
- Функция выбора, которая выбирает лучшего кандидата для добавления в решение.
- Функция осуществимости, которая используется, чтобы определить, можно ли использовать кандидата для внесения вклада в решение.
- Целевая функция, которая присваивает значение решению или частичному решению, и
- Функция решения, которая укажет, когда мы нашли полное решение.
Жадные алгоритмы дают хорошие решения для одних математических проблем , но не для других. У большинства проблем, с которыми они работают, будет два свойства:
- Жадный выбор собственности
- Мы можем сделать любой выбор, который кажется лучшим в данный момент, а затем решить подзадачи, которые возникнут позже. Выбор, сделанный жадным алгоритмом, может зависеть от выбора, сделанного на данный момент, но не от будущего выбора или всех решений подзадачи. Он итеративно делает один жадный выбор за другим, уменьшая каждую заданную проблему до более мелкой. Другими словами, жадный алгоритм никогда не пересматривает свой выбор. Это главное отличие от динамического программирования , которое является исчерпывающим и гарантированно находит решение. После каждого этапа динамическое программирование принимает решения на основе всех решений, принятых на предыдущем этапе, и может пересмотреть алгоритмический путь предыдущего этапа к решению.
- Оптимальная подконструкция
- «Проблема демонстрирует оптимальную подструктуру, если оптимальное решение проблемы содержит оптимальные решения подзадач». [2]
Случаи отказа [ править ]
Для многих других проблем жадные алгоритмы не дают оптимального решения и могут даже дать уникальное наихудшее решение. Одним из примеров является упомянутая выше задача коммивояжера : для каждого количества городов существует присвоение расстояний между городами, для которых эвристика ближайшего соседа дает уникальный наихудший возможный маршрут. [3]
Типы [ править ]
 | Этот раздел требует дополнительных ссылок для проверки . ( Июнь 2018 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) |
Жадные алгоритмы можно охарактеризовать как «близорукие», а также как «невосстановимые». Они идеальны только для задач с «оптимальной подструктурой». Несмотря на это, для многих простых задач лучше всего подходят жадные алгоритмы. Однако важно отметить, что жадный алгоритм может использоваться в качестве алгоритма выбора для определения приоритета опций в рамках поиска или алгоритма ветвей и границ. Есть несколько вариантов жадного алгоритма:
- Чистые жадные алгоритмы
- Ортогональные жадные алгоритмы
- Расслабленные жадные алгоритмы
Теория [ править ]
Жадные алгоритмы имеют долгую историю изучения комбинаторной оптимизации и теоретической информатики . Известно, что жадные эвристики дают неоптимальные результаты по многим проблемам [4], поэтому естественными вопросами являются:
- Для каких задач жадные алгоритмы работают оптимально?
- Для каких проблем жадные алгоритмы гарантируют приблизительно оптимальное решение?
- Для каких проблем жадный алгоритм гарантированно не даст оптимального решения?
Существует большой объем литературы, в которой даны ответы на эти вопросы как для общих классов задач, таких как матроиды , так и для конкретных задач, таких как набор покрытий .
Матроиды [ править ]
Матроидом представляет собой математическую структуру , которая обобщает понятие линейной независимости от векторных пространств на произвольные множества. Если задача оптимизации имеет структуру матроида, то соответствующий жадный алгоритм решит ее оптимальным образом. [5]
Субмодульные функции [ править ]
Функция , определенная на подмножествах множества называется субмодулярной , если для каждого у нас есть что .
Предположим, кто-то хочет найти набор, который максимизирует . Жадный алгоритм, который строит набор , постепенно добавляя элемент, который увеличивается больше всего на каждом шаге, выдает на выходе набор, который не меньше . [6] То есть, жадность работает с постоянным коэффициентом, равным оптимальному решению.
Аналогичные гарантии можно доказать, когда на выход накладываются дополнительные ограничения, такие как ограничения количества элементов [7] , хотя часто требуются небольшие изменения жадного алгоритма. См. Обзор [8] .
Другие проблемы с гарантиями [ править ]
К другим проблемам, для которых жадный алгоритм дает надежную гарантию, но не оптимальное решение, относятся:
- Установить обложку
- Проблема дерева Штейнера
- Балансировка нагрузки [9]
- Независимый набор
Многие из этих проблем имеют совпадающие нижние границы; т.е. жадный алгоритм в худшем случае не работает лучше, чем гарантированный.
Приложения [ править ]
Этот раздел нуждается в расширении . Вы можете помочь, добавив к нему . ( Июнь 2018 г. ) |
Жадные алгоритмы обычно (но не всегда) не могут найти глобально оптимальное решение, потому что они обычно не оперируют исчерпывающе для всех данных. Они могут слишком рано принять определенные решения, что помешает им найти лучшее общее решение позже. Например, все известные алгоритмы жадной раскраски для задачи раскраски графа и всех других NP-полных задач не всегда находят оптимальные решения. Тем не менее они полезны, потому что они быстро придумываются и часто дают хорошие приближения к оптимуму.
Если можно доказать, что жадный алгоритм дает глобальный оптимум для данного класса проблем, он обычно становится методом выбора, поскольку он быстрее, чем другие методы оптимизации, такие как динамическое программирование . Примерами таких жадных алгоритмов Алгоритм Крускала и алгоритм Прима для нахождения минимального остовного дерева , и алгоритм для нахождения оптимальных деревьев Хаффмана .
Жадные алгоритмы появляются и в сетевой маршрутизации . Используя жадную маршрутизацию, сообщение пересылается на соседний узел, который является «ближайшим» к месту назначения. Понятие местоположения узла (и, следовательно, «близость») может определяться его физическим местоположением, как при географической маршрутизации, используемой специальными сетями . Местоположение также может быть полностью искусственной конструкцией, как в случае с маршрутизацией в маленьком мире и распределенной хеш-таблицей .
Примеры [ править ]
- Проблема выбора деятельности характерна для этого класса задач, где цель состоит в том, чтобы выбрать максимальное количество действий, которые не конфликтуют друг с другом.
- В компьютерной игре « Кристалл Квест» для Macintosh цель - собирать кристаллы аналогично задаче коммивояжера . В игре есть демонстрационный режим, в котором игра использует жадный алгоритм для перехода к каждому кристаллу. Искусственный интеллект не учитывает препятствия, поэтому демонстрационный режим часто заканчивается быстро.
- Поиск совпадения является примером жадного алгоритма , нанесенного на приближении сигнала.
- Жадный алгоритм находит оптимальное решение проблемы Малфатти о нахождении трех непересекающихся кругов внутри данного треугольника, которые максимизируют общую площадь кругов; предполагается, что один и тот же жадный алгоритм оптимален для любого числа кругов.
- Жадный алгоритм используется для построения дерева Хаффмана во время кодирования Хаффмана, где он находит оптимальное решение.
- При изучении дерева решений обычно используются жадные алгоритмы, однако они не гарантируют нахождение оптимального решения.
- Одним из популярных таких алгоритмов является алгоритм ID3 для построения дерева решений.
- Алгоритм Дейкстров и соответствующий A * алгоритм поиска являются проверяемым оптимальными жадными алгоритмами поиска графов и кратчайшим путем нахождения .
- Поиск * является условно оптимальным и требует « допустимой эвристики », которая не будет переоценивать стоимость пути.
- Алгоритм Крускала и алгоритм Прима жадные алгоритмы для построения минимальных остовных деревьев из заданного связного графа . Они всегда находят оптимальное решение, которое в целом может быть не уникальным.
См. Также [ править ]
- Поиск по первому лучшему
- Эпсилон-жадная стратегия
- Жадный алгоритм для египетских дробей
- Жадный источник
- Matroid
Ссылки [ править ]
- ↑ Black, Paul E. (2 февраля 2005 г.). «жадный алгоритм» . Словарь алгоритмов и структур данных . Национальный институт стандартов и технологий США (NIST) . Проверено 17 августа 2012 года .
- ^ Кормен и др. 2001 , гл. 16
- ^ Гутин, Григорий; Йео, Андерс; Зверович, Алексей (2002). «Коммивояжер не должен быть жадным: анализ доминирования жадных эвристик для TSP». Дискретная прикладная математика . 117 (1–3): 81–86. DOI : 10.1016 / S0166-218X (01) 00195-0 .
- ^ Файги 1998
- ^ Papadimitriou & Штиглиц 1998
- ^ Nemhauser, Вулси & Fisher 1978
- ^ Buchbinder et al. 2014 г.
- ^ Краузе и Головин 2014
- ^ «Лекция 5: Введение в алгоритмы приближения» (PDF) . Продвинутые алгоритмы (2IL45) - Примечания к курсу . TU Eindhoven.
Источники [ править ]
- Cormen, Thomas H .; Leiserson, Charles E .; Ривест, Рональд Л .; Стейн, Клиффорд (2001). «16 жадных алгоритмов» . Введение в алгоритмы . MIT Press. С. 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 .
- Файги, У. (1998). «Порог ln n для аппроксимации обложки набора» (PDF) . Журнал ACM . 45 (4): 634–652. DOI : 10.1145 / 285055.285059 . S2CID 52827488 .
- Nemhauser, G .; Wolsey, LA; Фишер, 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.
- Krause, A .; Головин Д. (2014). «Максимизация субмодульных функций» . В Бордо, L .; Hamadi, Y .; Коли П. (ред.). Сговорчивость: практические подходы к трудным проблемам . Издательство Кембриджского университета. С. 71–104. DOI : 10.1017 / CBO9781139177801.004 . ISBN 9781139177801.
Внешние ссылки [ править ]
 | Викискладе есть медиафайлы по теме жадных алгоритмов . |
- «Жадный алгоритм» , Энциклопедия математики , EMS Press , 2001 [1994]
- Подарок, Ной. "Пример жадной монеты Python" .
