Лекция
Сразу хочу сказать, что здесь никакой воды про жадные алгоритмы, и только нужная информация. Для того чтобы лучше понимать что такое жадные алгоритмы, жадный алгоритм , настоятельно рекомендую прочитать все из категории Алгоритмы и теория алгоритмов.
жадный алгоритм — алгоритм, заключающийся в принятии локально оптимальных решений на каждом этапе, допуская, что конечное решение также окажется оптимальным. Известно, что если структура задачи задается матроидом, тогда применение жадного алгоритма выдаст глобальный оптимум.
жадный алгоритм (greedy algorithm) — это алгоритм, который на каждом шагу делает локально наилучший выбор в надежде, что итоговое решение будет оптимальным.
Если глобальная оптимальность алгоритма имеет место практически всегда, его обычно предпочитают другим методам оптимизации, таким как динамическое программирование.
жадные алгоритмы это такие алгоритмы, которые стремятся сделать оптимальный выбор в каждый момент времени. На каждом шагу выбирается лучший выбор, не задумываясь о будущем.
Почему жадные алгоритмы называются жадными?
Алгоритмы называются жадными, когда они используют жадное свойство. Жадное свойство:
В каждый момент времени, что есть лучший выбор?
Жадные алгоритмы — жадные. Они не смотрят в будущее, чтобы выбрать глобальное оптимальное решение. Их интересует только лучшее решение в данный момент. Но общее оптимальное решение может отличаться от решения, которое выбирает алгоритм на каждом шаге своей работы. Так же они никогда не оглядываются назад на то, что сделали, чтобы понять, нужна ли глобальная оптимизация. В этом главное отличие жадного и динамического программирования.
Для чего используются жадные алгоритмы?
Жадные алгоритмы очень быстрые. Намного быстрее, чем две другие альтернативы (Разделяй и властвуй — Divide & Conquer, и Динамическое программирование Dynamic Programming). Они популярные, потому что они быстрые.
Примеры популярных жадных алгоритмов:
Как мне создать жадный алгоритм?
Ваш алгоритм должен всегда отвечать на этот вопрос:
Каков лучший выбор в этот момент времени?
Общего критерия оценки применимости жадного алгоритма для решения конкретной задачи не существует, однако для задач, решаемых жадными алгоритмами, характерны две особенности: во-первых, к ним применим Принцип жадного выбора, а во-вторых, они обладают свойством Оптимальности для подзадач.
Говорят, что к оптимизационной задаче применим принцип жадного выбора, если последовательность локально оптимальных выборов дает глобально оптимальное решение. В типичном случае доказательство оптимальности следует такой схеме:
Говорят, что задача обладает свойством оптимальности для подзадач, если оптимальное решение задачи содержит в себе оптимальные решения для всех ее подзадач. Например, в задаче о выборе заявок можно заметить, что если 
— оптимальный набор заявок, содержащий заявку номер 1, то 
— оптимальный набор заявок для меньшего множества заявок 
, состоящего из тех заявок, для которых 
.
Задача. Монетная система некоторого государства состоит из монет достоинством 
. Об этом говорит сайт https://intellect.icu . Требуется выдать сумму {\displaystyle S}
наименьшим возможным количеством монет.
Жадный алгоритм решения этой задачи таков. Берется наибольшее возможное количество монет достоинства 
: 
. Таким же образом получаем, сколько нужно монет меньшего номинала, и т. д.
Для данной задачи жадный алгоритм не всегда дает оптимальное решение, а только для некоторых, называемых каноническими, монетных систем, вроде используемых в США (1, 5, 10, 25 центов). Неканонические системы таким свойством не обладают. Так, например, сумму в 24 копейки монетами в 1, 5 и 7 коп. жадный алгоритм разменивает так: 7 коп. — 3 шт., 1 коп. — 3 шт., в то время как правильное решение — 7 коп. — 2 шт., 5 коп. — 2 шт.
Формулировка № 1. Даны 
заявок на проведение занятий в некоторой аудитории. В каждой заявке указаны начало и конец занятия ( 
и 
для 
-й заявки). В случае пересечения заявок можно удовлетворить лишь одну из них. Заявки с номерами и 
совместны, если интервалы 
и 
не пересекаются (то есть 
или 
). Задача о выборе заявок состоит в том, чтобы набрать максимальное количество совместных друг с другом заявок.
Формулировка № 2. На конференции, чтобы отвести больше времени на неформальное общение, различные секции разнесли по разным аудиториям. Ученый с чрезвычайно широкими интересами хочет посетить несколько докладов, проходящих в разных секциях. Известно начало и конец каждого доклада. Определить, какое максимальное количество докладов можно посетить.
Приведем жадный алгоритм, решающий данную задачу. При этом полагаем, что заявки упорядочены в порядке возрастания времени окончания. Если это не так, то можно отсортировать их за время 
; заявки с одинаковым временем конца располагаем в произвольном порядке.
Activity-Selector(s,f)
length[s]
to doif 
then
На вход данному алгоритму подаются массивы начала и окончания занятий. Множество A состоит из номеров выбранных заявок, а j — номер последней заявки. Жадный алгоритм ищет заявку, начинающуюся не ранее окончания j-той, затем найденную заявку включает в A, а j присваивает ее номер. Таким образом, каждый раз мы выбираем то (еще не начавшееся) занятие, до конца которого осталось меньше всего времени.
Алгоритм работает за 
, то есть сортировка плюс выборка. На каждом шаге выбирается наилучшее решение. Покажем, что в итоге получится оптимум.
Доказательство. Заметим, что все заявки отсортированы по неубыванию времени окончания. Заявка номер 1, очевидно, входит в оптимум (если нет, то заменим самую раннюю заявку в оптимуме на нее, от этого хуже не станет). Выкинув все заявки, противоречащие первой, получим исходную задачу с меньшим количеством заявок. Рассуждая по индукции, аналогичным образом приходим к оптимальному решению.
Обобщением жадных алгоритмов является алгоритм Радо — Эдмондса.
Для ряда задач, относящихся к классу NP, жадные алгоритмы не дают оптимального решения. К ним относятся:
Тем не менее, в ряде задач жадные алгоритмы дают неплохие приближенные решения.
Жадная раскраска в теории графов — раскраска вершин неориентированного графа, созданная жадным алгоритмом, который проходит вершины графа в некоторой предопределенной последовательности и назначает каждой вершине первый доступный цвет. Жадные алгоритмы, в общем случае, не дают минимально возможное число цветов, однако они используются в математике в качестве техники доказательств других результатов, относящихся к раскраске, а также в компьютерных программах для получения раскраски с небольшим числом цветов.
Две раскраски жадным алгоритмом одного и того же графа, в которых используется различный порядок прохода вершин. Правый пример показывает, что граф с n вершинами, который можно раскрасить в два цвета, может быть раскрашен жадным алгоритмом в 
цветов.
Жадные алгоритмы не всегда хороши , например граф Корона (полный двудольный граф Kn,n с удаленными ребрами совершенного паросочетания) является особенно плохим случаем для жадного алгоритма — если в последовательности вершин поместить подряд две вершины, принадлежащие удаленному ребру из паросочетания, жадный алгоритм использует n цветов, в то время, как оптимальным числом для такого графа является два цвета. Существуют также графы, для которых с большой вероятностью случайно выбранная последовательность вершин приведет к использованию числа цветов, существенно большему минимально необходимого . Таким образом, очень важно осторожно выбирать последовательность, в которой вершины проходятся жадным алгоритмом.
Граф Короны с шестью, восемью и десятью вершинами вершин = 2 n ребер = n (n — 1)
Для заданного графа G и числа k, определение, существует ли порядок вершин графа G, который приводит к использованию жадным алгоритмом k и более цветов, является NP-полной задачей. Это, в частности, означает, что трудно найти наихудший случай для графа G .
Разделяй и властвуй
А как ты думаешь, при улучшении жадные алгоритмы, будет лучше нам? Надеюсь, что теперь ты понял что такое жадные алгоритмы, жадный алгоритм и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Алгоритмы и теория алгоритмов
Комментарии
Оставить комментарий
Алгоритмы и теория алгоритмов
Термины: Алгоритмы и теория алгоритмов