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

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

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

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

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

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

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

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

Говорят, что задача обладает свойством оптимальности для подзадач для выведения результата , если оптимальное решение задачи содержит в себе оптимальные решения для всех её подзадач. Например, в можно заметить, что если ${\displaystyle A}$ — оптимальный набор заявок, содержащий заявку номер 1, то ${\displaystyle A'=A\setminus \left\{1\right\}}$ — оптимальный набор заявок для меньшего множества заявок ${\displaystyle S'}$ , состоящего из тех заявок, для которых ${\displaystyle s_{i}\leqslant f_{1}}$ .

Примеры

Размен монет

Задача. Монетная система некоторого государства состоит из монет достоинством ${\displaystyle a_{1}=1<a_{2}<...<a_{n}}$ . Требуется выдать сумму ${\displaystyle S}$ наименьшим возможным количеством монет.

Жадный алгоритм решения этой задачи таков. Берётся наибольшее возможное количество монет достоинства ${\displaystyle a_{n}}$ : ${\displaystyle x_{n}=\lfloor S/a_{n}\rfloor }$ . Таким же образом получаем, сколько нужно монет меньшего номинала, и т. д.

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

Выбор заявок

Формулировка № 1. Даны ${\displaystyle n}$ заявок на проведение занятий в некоторой аудитории. В каждой заявке указаны начало и конец занятия ( ${\displaystyle s_{i}}$ и ${\displaystyle f_{i}}$ для ${\displaystyle i}$ -й заявки). В случае пересечения заявок можно удовлетворить лишь одну из них. Заявки с номерами ${\displaystyle i}$ и ${\displaystyle j}$ совместны, если интервалы ${\displaystyle [s_{i},f_{i})}$ и ${\displaystyle [s_{j},f_{j})}$ не пересекаются (то есть ${\displaystyle f_{i}\leqslant s_{j}}$ или ${\displaystyle f_{j}\leqslant s_{i}}$ ). Задача о выборе заявок состоит в том, чтобы набрать максимальное количество совместных друг с другом заявок.

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

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

Activity-Selector(s,f)

1. ${\displaystyle n\leftarrow }$ length[s]
2. ${\displaystyle A\leftarrow \left\{1\right\}}$
3. ${\displaystyle j\leftarrow 1}$
4. for ${\displaystyle i\leftarrow 2}$ to ${\displaystyle n}$ do

   if ${\displaystyle s_{i}\geq f_{j}}$ then

   ${\displaystyle A\leftarrow A\cup \{i\}}$

   ${\displaystyle j\leftarrow i}$

5. return A

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

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

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

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

• Алгоритм Хаффмана (адаптивный алгоритм оптимального префиксного кодирования алфавита с минимальной избыточностью).
• Алгоритм Крускала (поиск остовного дерева минимального веса в графе).
• Алгоритм Прима (поиск остовного дерева минимального веса в связном графе).

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

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

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

• задача коммивояжера ;
• задача минимальной раскраски графа ;
• задача разбиения графа на подграфы ;
• задача выделения максимальной клики ;
• задачи, связанные с составлением расписаний .

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

См. также

• Жадность (регулярные выражения)
• Категория:Задачи, решаемые жадным алгоритмом

Примечания

Литература

• Кормен, Т. , Лейзерсон, Ч. , Ривест, Р. , Штайн, К. // Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М. : Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4 .

Ссылки

• Видеозапись лекции в Computer Science центре