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

Поделись знанием:
(перенаправлено с «ЖА»)
Перейти к: навигация, поиск

Жадный алгоритм (англ. Greedy algorithm) — алгоритм, заключающийся в принятии локально оптимальных решений на каждом этапе, допуская, что конечное решение также окажется оптимальным. Известно, что если структура задачи задается матроидом, тогда применение жадного алгоритма выдаст глобальный оптимум.

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





Условия применимости

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

Принцип жадного выбора

Говорят, что к оптимизационной задаче применим принцип жадного выбора, если последовательность локально оптимальных выборов даёт глобально оптимальное решение. В типичном случае доказательство оптимальности следует такой схеме:

  1. Доказывается, что жадный выбор на первом шаге не закрывает пути к оптимальному решению: для всякого решения есть другое, согласованное с жадным выбором и не хуже первого.
  2. Показывается, что подзадача, возникающая после жадного выбора на первом шаге, аналогична исходной.
  3. Рассуждение завершается по индукции.

Оптимальность для подзадач

Говорят, что задача обладает свойством оптимальности для подзадач, если оптимальное решение задачи содержит в себе оптимальные решения для всех её подзадач. Например, в задаче о выборе заявок можно заметить, что если <math>A</math> — оптимальный набор заявок, содержащий заявку номер 1, то <math>A^\prime = A \setminus \left\{1\right\}</math>— оптимальный набор заявок для меньшего множества заявок <math>S^\prime</math>, состоящего из тех заявок, для которых <math>s_i \le f_1</math>.

Примеры

Размен монет

Задача. Монетная система некоторого государства состоит из монет достоинством <math>a_1=1 < a_2 < ... < a_n</math>. Требуется выдать сумму <math>S</math> наименьшим возможным количеством монет.

Жадный алгоритм решения этой задачи таков. Берётся наибольшее возможное количество монет достоинства <math>a_n</math>: <math>x_n=\lfloor S/a_n \rfloor</math>. Таким же образом получаем, сколько нужно монет меньшего номинала, и т. д.

Для данной задачи жадный алгоритм не всегда даёт оптимальное решение, а только для некоторых, называемых каноническими, монетных систем, вроде используемых в США (1, 5, 10, 25 центов). Неканонические системы таким свойством не обладают. Так, например, сумму в 24 копейки монетами в 1, 5 и 7 коп. жадный алгоритм разменивает так: 7 коп. — 3 шт., 1 коп. — 3 шт., в то время как правильное решение — 7 коп. — 2 шт., 5 коп. — 2 шт.[1]

Выбор заявок

Формулировка № 1. Даны <math>n</math> заявок на проведение занятий в некоторой аудитории. В каждой заявке указаны начало и конец занятия (<math>s_i</math> и <math>f_i</math> для <math>i</math>-й заявки). В случае пересечения заявок можно удовлетворить лишь одну из них. Заявки с номерами <math>i</math> и <math>j</math> совместны, если интервалы <math>[s_i, f_i)</math> и <math>[s_j, f_j)</math> не пересекаются (то есть <math>f_i \le s_j</math> или <math>f_j \le s_i</math>). Задача о выборе заявок состоит в том, чтобы набрать максимальное количество совместных друг с другом заявок.

Формулировка № 2. На конференции, чтобы отвести больше времени на неформальное общение, различные секции разнесли по разным аудиториям. Учёный с чрезвычайно широкими интересами хочет посетить несколько докладов, проходящих в разных секциях. Известно начало <math>s_i</math> и конец <math>f_i</math> каждого доклада. Определить, какое максимальное количество докладов можно посетить.

Приведём жадный алгоритм, решающий данную задачу. При этом полагаем, что заявки упорядочены в порядке возрастания времени окончания. Если это не так, то можно отсортировать их за время <math>O(n \log n)</math>; заявки с одинаковым временем конца располагаем в произвольном порядке.

Activity-Selector(s,f)

  1. <math>n \leftarrow</math> length[s]
  2. <math>A \leftarrow \left\{1\right\}</math>
  3. <math>j \leftarrow 1</math>
  4. for <math>i \leftarrow 2</math> to <math>n</math> do
    if <math>s_i \ge f_j</math> then
    <math>A \leftarrow A \cup \{i\}</math>
    <math>j \leftarrow i</math>
  5. return A

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

Алгоритм работает за <math>O(n \log n+n)</math>, то есть сортировка плюс выборка. На каждом шаге выбирается наилучшее решение. Покажем, что в итоге получится оптимум.

Доказательство. Заметим, что все заявки отсортированы по неубыванию времени окончания. Заявка номер 1, очевидно, входит в оптимум (если нет, то заменим самую раннюю заявку в оптимуме на неё, от этого хуже не станет). Выкинув все заявки, противоречащие первой, получим исходную задачу с меньшим количеством заявок. Рассуждая по индукции, аналогичным образом приходим к оптимальному решению.

Другие жадные алгоритмы

Обобщением жадных алгоритмов является алгоритм Радо — Эдмондса.

Задачи, в которых жадные алгоритмы не дают оптимального решения

Для ряда задач, относящихся к классу NP, жадные алгоритмы не дают оптимального решения. К ним относятся:

Тем не менее, в ряде задач жадные алгоритмы дают неплохие приближённые решения.

См. также

Напишите отзыв о статье "Жадный алгоритм"

Примечания

  1. ↑ X. Cai [arxiv.org/PS_cache/arxiv/pdf/0809/0809.0400v1.pdf Canonical Coin Systems for Change-Making Problems] (англ.) // Proceedings of the Ninth International Conference on Hybrid Intelligent Systems. — 2009. — P. 499–504. — DOI:10.1109/HIS.2009.103. — arXiv:0809.0400.

Литература

Ссылки

  • [compscicenter.ru/program/lecture/5163 Жадные алгоритмы] Видеозапись лекции в Computer Science центре
  • [rain.ifmo.ru/cat/view.php/theory/algorithm-analysis/greedy-2004 Дискретная математика: Жадные алгоритмы] @ ИТМО

Отрывок, характеризующий Жадный алгоритм

– Изволите видеть, мой любезнейший, записку я вашу читал, – перебил Аракчеев, только первые слова сказав ласково, опять не глядя ему в лицо и впадая всё более и более в ворчливо презрительный тон. – Новые законы военные предлагаете? Законов много, исполнять некому старых. Нынче все законы пишут, писать легче, чем делать.
– Я приехал по воле государя императора узнать у вашего сиятельства, какой ход вы полагаете дать поданной записке? – сказал учтиво князь Андрей.
– На записку вашу мной положена резолюция и переслана в комитет. Я не одобряю, – сказал Аракчеев, вставая и доставая с письменного стола бумагу. – Вот! – он подал князю Андрею.
На бумаге поперег ее, карандашом, без заглавных букв, без орфографии, без знаков препинания, было написано: «неосновательно составлено понеже как подражание списано с французского военного устава и от воинского артикула без нужды отступающего».
– В какой же комитет передана записка? – спросил князь Андрей.
– В комитет о воинском уставе, и мною представлено о зачислении вашего благородия в члены. Только без жалованья.
Князь Андрей улыбнулся.
– Я и не желаю.
– Без жалованья членом, – повторил Аракчеев. – Имею честь. Эй, зови! Кто еще? – крикнул он, кланяясь князю Андрею.


Ожидая уведомления о зачислении его в члены комитета, князь Андрей возобновил старые знакомства особенно с теми лицами, которые, он знал, были в силе и могли быть нужны ему. Он испытывал теперь в Петербурге чувство, подобное тому, какое он испытывал накануне сражения, когда его томило беспокойное любопытство и непреодолимо тянуло в высшие сферы, туда, где готовилось будущее, от которого зависели судьбы миллионов. Он чувствовал по озлоблению стариков, по любопытству непосвященных, по сдержанности посвященных, по торопливости, озабоченности всех, по бесчисленному количеству комитетов, комиссий, о существовании которых он вновь узнавал каждый день, что теперь, в 1809 м году, готовилось здесь, в Петербурге, какое то огромное гражданское сражение, которого главнокомандующим было неизвестное ему, таинственное и представлявшееся ему гениальным, лицо – Сперанский. И самое ему смутно известное дело преобразования, и Сперанский – главный деятель, начинали так страстно интересовать его, что дело воинского устава очень скоро стало переходить в сознании его на второстепенное место.
Князь Андрей находился в одном из самых выгодных положений для того, чтобы быть хорошо принятым во все самые разнообразные и высшие круги тогдашнего петербургского общества. Партия преобразователей радушно принимала и заманивала его, во первых потому, что он имел репутацию ума и большой начитанности, во вторых потому, что он своим отпущением крестьян на волю сделал уже себе репутацию либерала. Партия стариков недовольных, прямо как к сыну своего отца, обращалась к нему за сочувствием, осуждая преобразования. Женское общество, свет , радушно принимали его, потому что он был жених, богатый и знатный, и почти новое лицо с ореолом романической истории о его мнимой смерти и трагической кончине жены. Кроме того, общий голос о нем всех, которые знали его прежде, был тот, что он много переменился к лучшему в эти пять лет, смягчился и возмужал, что не было в нем прежнего притворства, гордости и насмешливости, и было то спокойствие, которое приобретается годами. О нем заговорили, им интересовались и все желали его видеть.
На другой день после посещения графа Аракчеева князь Андрей был вечером у графа Кочубея. Он рассказал графу свое свидание с Силой Андреичем (Кочубей так называл Аракчеева с той же неопределенной над чем то насмешкой, которую заметил князь Андрей в приемной военного министра).
– Mon cher, [Дорогой мой,] даже в этом деле вы не минуете Михаил Михайловича. C'est le grand faiseur. [Всё делается им.] Я скажу ему. Он обещался приехать вечером…
– Какое же дело Сперанскому до военных уставов? – спросил князь Андрей.
Кочубей, улыбнувшись, покачал головой, как бы удивляясь наивности Болконского.
– Мы с ним говорили про вас на днях, – продолжал Кочубей, – о ваших вольных хлебопашцах…
– Да, это вы, князь, отпустили своих мужиков? – сказал Екатерининский старик, презрительно обернувшись на Болконского.
– Маленькое именье ничего не приносило дохода, – отвечал Болконский, чтобы напрасно не раздражать старика, стараясь смягчить перед ним свой поступок.
– Vous craignez d'etre en retard, [Боитесь опоздать,] – сказал старик, глядя на Кочубея.
– Я одного не понимаю, – продолжал старик – кто будет землю пахать, коли им волю дать? Легко законы писать, а управлять трудно. Всё равно как теперь, я вас спрашиваю, граф, кто будет начальником палат, когда всем экзамены держать?
– Те, кто выдержат экзамены, я думаю, – отвечал Кочубей, закидывая ногу на ногу и оглядываясь.
– Вот у меня служит Пряничников, славный человек, золото человек, а ему 60 лет, разве он пойдет на экзамены?…
– Да, это затруднительно, понеже образование весьма мало распространено, но… – Граф Кочубей не договорил, он поднялся и, взяв за руку князя Андрея, пошел навстречу входящему высокому, лысому, белокурому человеку, лет сорока, с большим открытым лбом и необычайной, странной белизной продолговатого лица. На вошедшем был синий фрак, крест на шее и звезда на левой стороне груди. Это был Сперанский. Князь Андрей тотчас узнал его и в душе его что то дрогнуло, как это бывает в важные минуты жизни. Было ли это уважение, зависть, ожидание – он не знал. Вся фигура Сперанского имела особенный тип, по которому сейчас можно было узнать его. Ни у кого из того общества, в котором жил князь Андрей, он не видал этого спокойствия и самоуверенности неловких и тупых движений, ни у кого он не видал такого твердого и вместе мягкого взгляда полузакрытых и несколько влажных глаз, не видал такой твердости ничего незначащей улыбки, такого тонкого, ровного, тихого голоса, и, главное, такой нежной белизны лица и особенно рук, несколько широких, но необыкновенно пухлых, нежных и белых. Такую белизну и нежность лица князь Андрей видал только у солдат, долго пробывших в госпитале. Это был Сперанский, государственный секретарь, докладчик государя и спутник его в Эрфурте, где он не раз виделся и говорил с Наполеоном.
Сперанский не перебегал глазами с одного лица на другое, как это невольно делается при входе в большое общество, и не торопился говорить. Он говорил тихо, с уверенностью, что будут слушать его, и смотрел только на то лицо, с которым говорил.


Источник — «http://wiki-org.ru/wiki/index.php?title=Жадный_алгоритм&oldid=79728429»