Jump to content

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

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

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

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

Особенности

[ редактировать ]

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

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

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

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

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

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

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

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

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

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

Матроиды

[ редактировать ]

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

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

[ редактировать ]

Функция определено на подмножествах множества называется субмодулярным, если для любого у нас есть это .

Предположим, кто-то хочет найти набор который максимизирует . Жадный алгоритм, создающий множество путем постепенного добавления элемента, который увеличивает наибольшее количество на каждом шаге, выдает на выходе набор, который по крайней мере . [7] То есть жадность работает в пределах постоянного коэффициента так же хорошо, как оптимальное решение.

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

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

[ редактировать ]

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

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

Приложения

[ редактировать ]

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

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

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

См. также

[ редактировать ]
  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. ^ ДеВор, РА; Темляков В.Н. (12.1996). «Некоторые замечания о жадных алгоритмах» . Достижения в области вычислительной математики . 5 (1): 173–187. дои : 10.1007/BF02124742 . ISSN   1572-9044 .
  5. ^ Файги, 1998 г.
  6. ^ Пападимитриу и Стейглиц, 1998 г.
  7. ^ Немхаузер, Вулси и Фишер, 1978 г.
  8. ^ Бухбиндер и др. 2014 год
  9. ^ Краузе и Головин 2014.
  10. ^ «Лекция 5: Введение в алгоритмы аппроксимации» (PDF) . Расширенные алгоритмы (2IL45) — Конспекты курса . ТУ Эйндховена. Архивировано (PDF) из оригинала 9 октября 2022 г.

Источники

[ редактировать ]
[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: ff05a8282e514b7b8ef921010cbecf0e__1720017420
URL1:https://arc.ask3.ru/arc/aa/ff/0e/ff05a8282e514b7b8ef921010cbecf0e.html
Заголовок, (Title) документа по адресу, URL1:
Greedy algorithm - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)