что такое жадный алгоритм

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

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

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

Содержание

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

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

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

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

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

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

Примеры

Размен монет

Задача. Монетная система некоторого государства состоит из монет достоинством . Требуется выдать сумму наименьшим возможным количеством монет.

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

Для данной задачи жадный алгоритм не всегда даёт оптимальное решение. Например, сумму в 24 копейки монетами в 1, 5 и 7 коп. жадный алгоритм разменивает так: 7 коп. — 3 шт., 1 коп. — 3 шт., в то время как правильное решение — 7 коп. — 2 шт., 5 коп. — 2 шт. Тем не менее, на всех реальных монетных системах жадный алгоритм даёт правильный ответ.

Выбор заявок

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

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

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

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

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

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

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

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

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

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

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

Источник

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

Что такое жадный алгоритм?

В GREEDY ALGORITHM набор ресурсов рекурсивно разделяется на основе максимальной, немедленной доступности этого ресурса на любом этапе выполнения.

Чтобы решить проблему, основанную на жадном подходе, есть два этапа

Эти этапы выполняются параллельно по ходу деления массива.

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

Два условия определяют жадную парадигму.

Продолжив теоретизирование, давайте опишем историю, связанную с жадным подходом.

В этом уроке Greedy вы узнаете:

История жадных алгоритмов

Вот важный ориентир жадных алгоритмов:

Жадные стратегии и решения

Логика в ее самой простой форме сводилась к «жадному» или «не жадному». Эти утверждения были определены подходом, принятым для продвижения на каждой стадии алгоритма.

Например, алгоритм Джикстра использовал пошаговую жадную стратегию, идентифицирующую хосты в Интернете путем вычисления функции стоимости. Значение, возвращаемое функцией стоимости, определяет, является ли следующий путь «жадным» или «не жадным».

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

Характеристики жадного подхода

Важными характеристиками жадного метода являются:

Зачем использовать жадный подход?

Вот причины использования жадного подхода:

Как решить проблему выбора активности

В примере планирования действий есть время «начала» и «окончания» для каждого действия. Каждое мероприятие индексируется номером для справки. Есть две категории деятельности.

Общая продолжительность дает стоимость выполнения действия. То есть (финиш — старт) дает нам длительность как стоимость деятельности.

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

Архитектура Жадного подхода

ШАГ 1)

Сканирование списка затрат на деятельность, начиная с индекса 0 в качестве рассматриваемого индекса.

ШАГ 2)

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

ШАГ 3)

Если оставшихся действий больше нет, текущее оставшееся действие становится следующим рассматриваемым действием. Повторите шаги 1 и 2 для новой рассматриваемой операции. Если не осталось никаких действий, перейдите к шагу 4.

Источник

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

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

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

Содержание

Применимость жадных алгоритмов

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

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

Свойство оптимальности для подзадач

Говорят, что задача обладает свойством оптимальности для подзадач, если оптимальное решение задачи содержит в себе оптимальные решения для всех её подзадач. Например, в задаче о выборе заявок можно заметить, что если A — оптимальный набор заявок, содержащий заявку номер 1, то — оптимальный набор заявок для меньшего множества заявок , состоящего из тех заявок, для которых .

Примеры

Размен монет

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

Для данной задачи жадный алгоритм не всегда даёт оптимальное решение. Например, сумму в 10 копеек монетами в 1, 5 и 6 коп. жадный алгоритм разменивает так: 6 коп. — 1 шт., 1 коп. — 4 шт., в то время как правильное решение — 2 монеты по 5 копеек. Тем не менее, на всех реальных монетных системах жадный алгоритм даёт правильный ответ.

Выбор заявок

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

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

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

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

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

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

Источник

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

Доброго времени суток, хабр! Сегодня я бы хотел рассказать про жадные алгоритмы.

Есть много методов решения тех или иных задач: динамическое программирование, перебор. Не менее известными и довольно распространенными являются жадные алгоритмы.

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

Жадность не порок

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

К слову, алгоритм Флойда, который тоже ищет кратчайшие пути в графе (правда, между всеми вершинами), не является примером жадного алгоритма. Флойд демонстрирует другой метод — метод динамического программирования.

Использование жадного алгоритма довольно стандартное. Рассмотрим его на примере следующей задачи:

Задача о расписании

Пусть программисту-фрилансеру Васе Пупкину дано n заданий. У каждого задания известен свой дедлайн, а также его стоимость(то есть если он не выполняет это задание, то он теряет столько-то денег). Вася настолько крут, что за один день может сделать одно задание. Выполнение задания можно начать с момента 0. Нужно максимизировать прибыль.

Классический пример применения жадины: Васе выгодно делать самые «дорогие задания», а наименее дорогие можно и не выполнять — тогда прибыль будет максимальна. Возникает вопрос: каким образом распределить задания? Будем перебирать задания в порядке убывания стоимости и заполнять расписание следующим образом: если для заказа есть еще хотя бы одно свободное место в расписании раньше его дедлайна, то поставим его на самое последнее из таких мест, в противном случае в срок мы его не можем выполнить, значит поставим в конец из свободных мест.

Получается следующий код:

Когда можно быть жадным?

Всегда Иногда может возникнуть искушение использовать жадину везде, где только это возможно, но на некоторых задачах это неприемлимо. К примеру, задача о рюкзаке: вор пробрался на склад, в котором хранятся три вещи весом 10 кг, 20 кг и 30 кг и стоимостью 60, 100 и 120 деревянных вечнозеленых нанорублей соответственно. Вор максимум может унести 50 кг. Нужно максимизировать прибыль вора. Если поступать здесь жадно и выбирать самую ценную вещь(то есть, 6 нанорублей за кг первой штуки, 5 нанорублей за кг второй и 4 нанорубля за кг третьей), то вор по-любому должен взять первую вещь, потом останется место для второй вещи, однако оптимальное решение составляет вторая и третья вещь.

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

Жизнь не матроид, жизнь — конечный автомат!

Как подсказывает википедия, матроид — это пара (X, I), где X — конечное множество, называемое носителем матроида, а I — некоторое множество подмножеств X, называемое семейством независимых множеств. При этом должны выполняться следующие условия:

Источник

Алгоритмы — часть 1. Жадные алгоритмы, алгоритм Дейкстры.

Эта отрывок из бесплатной книги «Парадигмы алгоритмического проектирования (жадные алгоритмы, разделяй и властвуй и динамическое программирование)» —Brandon Algorithmic Design Paradigms (Greedy, Divide & Conquer, and Dynamic Programming).. ✨

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

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

Почему жадные алгоритмы называются жадными?

Алгоритмы называются жадными, когда они используют жадное свойство. Жадное свойство:

В каждый момент времени, что есть лучший выбор?

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

Для чего используются жадные алгоритмы?

Жадные алгоритмы очень быстрые. Намного быстрее, чем две другие альтернативы (Разделяй и властвуй — Divide & Conquer, и Динамическое программирование Dynamic Programming). Они популярные, потому что они быстрые.

Примеры популярных жадных алгоритмов:

Мы собираемся рассмотреть жадные алгоритмы, на известном примере — подсчет выдачи сдачи. Это не так сложно для этой парадигмы.

Как мне создать жадный алгоритм?

Ваш алгоритм должен всегда отвечать на этот вопрос:

Каков лучший выбор в этот момент времени?

Вот и все. Не так уж и много. Жадные алгоритмы, как правило, легче кодировать, чем «разделяй и властвуй»(Divide & Conquer) или динамическое программирование (Dynamic Programming).

Подсчет выдачи сдачи используя жадность

Представьте, что вы торговый автомат. Кто-то дает вам £1 и покупает напиток за £0,70. В фунте стерлингов нет монеты 30 пенсов (30p). Как рассчитать, сколько сдачи вернуть?

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

Жадный алгоритм начинается с самого высокого номинала и работает в обратном направлении. Наш алгоритм начинается с £1.
£1 фунт больше, чем 30 пенсов, поэтому он не может его использовать. Далее смотрим на 50р, видим то же самое. Потом 20р. 20p 10p. Затем идет до 10р. Он выбирает 1 монету на 10p, и теперь возвращается 0, мы останавливаем алгоритм.

Итого мы возвращаем 1x20p и 1x10p.

Этот алгоритм работает довольно хорошо в реальной жизни. Давайте рассмотрим другой пример, на этот раз у нас есть номинал и количество этой монеты в автомате в формате (номинал, количество).

Алгоритм попросили снова вернуть сдачу на 30p. 100р (£ 1) — это нет. То же самое для 50. Далее 20p, мы можем сделать это. Мы выбираем 1x 20p. Теперь нам нужно вернуть 10р. 20p закончилось, поэтому мы идем вниз на 1 номинал.

10p закончилось, поэтому мы идем далее вниз еще на 1 номинал.

У нас 5p, поэтому мы выбираем 1x5p. Теперь нам нужно вернуть еще 5р. Проверяем 5p но они закончились, поэтому мы спускаемся вниз.

Мы выбираем 1 монету на 2p. Теперь нам нужно вернуть 3р. Мы выбираем еще 2 монеты. Теперь нам нужно вернуть 1р. Мы спускаемся еще раз вниз. Тут мы выбираем 1x1p монета.

В общем, наш алгоритм выбрал следующие монеты, чтобы вернуть сдачу:

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

Теперь перейдем к основной функции. С учетом номиналов и суммы для внесения изменений мы хотим вернуть список того, сколько раз эта монета была возвращена.

Если наш список denominations такой же, как указано выше, то [6, 3, 0, 0, 0, 0, 0] представляет собой взятие 6 монет 1p и 3 монет 2p, но 0 всех других монет.

Создаем полный список denominations и отствующие значения заполним нулями.

Мы хотим пройтись от самого большого до самого маленького. Reversed(x) переворачивает x и позволяет нам зацикливаться в обратном направлении. Enumerate означает «цикл по этому списку, но сохраняйте позицию в другой переменной». В нашем примере, когда мы запускаем цикл. coin = 100 и pos = 6.

Наш следующий шаг — многократный выбор монеты, пока мы можем использовать эту монету. Если нам нужно дать сдачу change = 40, мы хотим, чтобы наш алгоритм выбрал 20, затем снова 20, пока он больше не сможет использовать 20. Мы делаем это с помощью цикла for.

В то время как coin все еще меньше или равно change, добавим эту coin в наш список возврата toGiveBack и удалим ее из сдачи.

Является ли жадный алгоритм лучшим? Жадность всегда работает?

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

Допустим у нас есть условие:

И нас попросим выдать сдачу в 30 пенсов. Теперь посмотрим, что вернет наш алгоритм.

То есть он выбирает 1x25p и 5x1p. Хотя лучшим решением будет — 2х15р.

Наш алгоритм потерпел неудачу, потому что он вообще не смотрел на 15p. Он первым делом посмотрел на 25р и подумал: «Да, это подходит. Давайте возьмем это».

Затем он посмотрел на 15p и подумал, что «это не подходит, давайте двигаться дальше» (так как 25 + 15 > 30).

Это пример того, где жадные алгоритмы не лучший выбор.

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

Существуют и другие глобально оптимальные решения, но жадные алгоритмы быстрее и проще в программировании, чем другие решения.

Алгоритм Дейкстры

Алгоритм Дейкстры находит кратчайший путь от узла ко всем остальным узлам графа. В нашем примере мы будем использовать взвешенный ориентированный граф. У каждого ребра есть направление, и у каждого ребра есть вес.

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

Алгоритм следует следующим правилам:

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

Мы отмечаем A в нашем списке не посещенных узлов. Расстояние от A до A равно 0. Расстояние от A до B равно 4. Расстояние от A до C равно 2. Наш список расстояний с правой стороны рисунка.

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

Мы можем добраться до B из C. Теперь нам нужно выбрать минимум. min(4, 2 + 1) = 3.

Поскольку A->C->B меньше, чем A->B, мы обновляем B этой информацией. Затем мы добавляем расстояния от других узлов, которые теперь можем достичь.

Наша следующая наименьшая вершина с узлом, который мы еще не посетили, это B, с 3. Мы посещаем B.

Мы делаем то же самое для B. Затем мы выбираем самую маленькую вершину, которую мы еще не посетили, D.

На этот раз мы не обновляем расстояния. Наш последний узел тогда E.

Там нет обновлений снова. Чтобы найти кратчайший путь от A до других узлов, мы пройдемся по нашему графику.

Сначала мы выбираем A, затем C, а затем B. Если вам нужно создать кратчайший путь от A до каждого другого узла в виде графика, вы можете запустить этот алгоритм, используя таблицу с правой стороны.

Используя эту таблицу легко нарисовать кратчайшее расстояние от A до каждого другого узла на графике:

Дробная задача о ранце с использованием жадного алгоритма

Представь, что ты вор. Ты врываешься в дом Джуди Холлидей — обладателя Оскара 1951 года за лучшую женскую роль. Джуди кладезь драгоценных камней. Дом Джуди выложен до краев драгоценными камнями.

Ты принес с собой сумку — рюкзак. Максимальный вместимость этой сумки — 7 пунктов веса. У тебя был список всех предметов Джуди из какой-то страховой бумаги. Пункты читаются как:

Первым шагом к решению проблемы дробного ранца является расчет стоимости/веса для каждого предмета.

И теперь мы жадно отбираем самые крупные. Для этого мы можем отсортировать их по значению/весу в порядке убывания. К счастью для нас, они уже отсортированы. Самый большой — 3,2.

Затем мы выбираем Francium (я знаю, что это не драгоценный камень, но Джуди немного странная 😉)

Теперь мы добавляем Сапфир. Но если мы добавим Сапфир, наш общий вес достигнет 8 пунктов.

В задаче дробного ранца мы можем разрезать предметы, чтобы взять их дроби. У нас в сумке осталось 1 пункт веса. Наш сапфир имеет вес 2 пункта. Мы рассчитываем соотношение:

Свободное место в рюкзаке / вес товара

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

1/2 * 6 = 3

Жадный алгоритм может оптимально решить проблему дробного ранца, но он не может оптимально решить проблему ранцев . В этой задаче вместо того, чтобы брать часть элемента, вы либо берете его , либо не берете . Чтобы решить эту проблему, вам нужно использовать динамическое программирование.

Сложность алгоритма для него O(n log n). Расчетное значение/вес O (1). Наш основной шаг — сортировка по наибольшему значению/весу, что занимает O(n log n) времени.

Заключение

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

Источник